C++小白训练第二天

C++小白训练第二天

以下为牛客挑战
今日收获

1. s[i]如果为前缀和，那么一段区间的和为，s[r-1]-s[l];
2. 后缀的时候我们一定要（n+2）
4. 知道了怎么求数的叶子节点个数的多少
5. cin>>u>>v;
6. dg[u]++,dg[v]++;

复制代码

牛客挑战125

小苯的数组操作

E-小苯的数组操作_牛客周赛 Round 125

1. 1
2. 8 4
3. 6 2 4 1 5 3 4 6
4. 1 2
5. 3
6. 2 6
7. 3

复制代码

1. 27
2. 23

复制代码

这个题的思路就是
我们可以分两种情况去讨论

• 当l和r没有交在一起时候，我们可以明显得到s1L+s2(n-R+1)+s[R-1]-s[L]**这个公式
  

1. s1原本的表示是前面的最小值，s2后面的最小值，s[R-1]-s[L]然后后面的就是区间和，s是前缀和

复制代码

• 当这个存在交集时候我们可以直接分两种情况去判断，一个是L覆盖R那么L这一边全部变成数列中的最小值。
  
• 当这个存在交集时候我们可以直接分两种情况去判断，一个是R覆盖L那么R这一边全部变成数列中的最小值。
  

但是我们可以讲起分成两段，被覆盖的一边退回原来的位置，就可以当成没有重合的两段做。

1. s1*L+s2*(n-R+1)+s[R-1]-s[L]

复制代码

解题代码

[code]#include#define int long long#define lll __uint128_t#define PII pair#define endl '\n'using namespace std;#define yn(ans) printf("%s\n", (ans)?"Yes":"No");//快速打印#define YN(ans) printf("%s\n", (ans)?"YES":"NO");#define REP(i, e) for (int i = 0; i < (e); ++i)#define REP1(i, s, e) for (int i = (s); i > t; while (t--)#define TESTconst int N=3e5+10,M=1e3+10,mod=1e9+7;void solve(){    int n,q;    cin>>n>>q;    vectora(n+1),s(n+1);//数组，和前缀和    vectorpre(n+1,1e9);//前缀最小值    vectorsuf(n+2,1e9);//后缀最小值    int L=0,R=n+1;    int s1=pre[1],s2=pre[n];    for(int i=1;i>a;        s=s[i-1]+a;        pre=min(pre[i-1],a);    }    for(int i=n;i>0;i--){        suf=min(suf[i+1],a);    }    while(q--){        int op;        cin>>op;        if(op==1){            int i;            cin>>i;            L=max(i,L);//就是选过的之前的区间，如果是子区间，直接用父区间来就行了            if(L>i;            R=min(i,R);            if(LB;    if(A>B){       cout>f;    int x1=(d-b)*(d-b)+(c-a)*(c-a);    int x2=(f-d)*(f-d)+(e-c)*(e-c);    int x3=(f-b)*(f-b)+(e-a)*(e-a);    if(x1==x2&&x2==x3){        cout=(m-1)){        cout