非常简单的单点修改+区间加+区间查询。我用的是最近刚学的区间修改版本树状数组。
直接维护即可，注意修改后的单点值已经不是a[i]，或者b[i]，要通过区间查询求单点。不然是错的。
区间修改版本树状数组：
#include<iostream> #include<string.h> #include<stdio.h> #include<algorithm> #define LL long long using namespace std; LL c_p[400005]; LL sum_p[400005]; LL c_y[400005]; LL sum_y[400005]; LL a[200005]; LL b[200005]; int n,m; int cnt1; int cnt2; int lowbit(int x){ return x&(-x); } void update(int x,int w,LL c[],LL sum[]){ for (int i=x;i<=n;i+=lowbit(i)){ c[i]+=(LL)w; sum[i]+=(LL)w*(x-1); } } LL sum(int x,LL c[],LL sum[]){ LL ans=0; for (int i=x;i>0;i-=lowbit(i)){ ans+=(LL)x*c[i]-sum[i]; } return ans; } int main(){ while(~scanf("%d%d",&n,&m)){ a[0]=0; cnt1=0; cnt2=0; for (int i=1;i<=n;i++){ scanf("%lld",&a[i]); update(i,a[i]-a[i-1],c_p,sum_p); } b[0]=0; for (int i=1;i<=n;i++){ scanf("%lld",&b[i]); update(i,b[i]-b[i-1],c_y,sum_y); } int ss=0; while(m--){ ss++; char op[10]; char to; int x,y,w; scanf("%s",op); if (op[1]=='i'){ scanf(" %c",&to); scanf("%d%d",&x,&y); if (to=='P'){ int lw=sum(x,c_p,sum_p)-sum(x-1,c_p,sum_p); int rw=sum(y,c_p,sum_p)-sum(y-1,c_p,sum_p); update(x,rw-lw,c_p,sum_p); update(x+1,lw-rw,c_p,sum_p); update(y,lw-rw,c_p,sum_p); update(y+1,rw-lw,c_p,sum_p); }else { int lw=sum(x,c_y,sum_y)-sum(x-1,c_y,sum_y); int rw=sum(y,c_y,sum_y)-sum(y-1,c_y,sum_y); update(x,rw-lw,c_y,sum_y); update(x+1,lw-rw,c_y,sum_y); update(y,lw-rw,c_y,sum_y); update(y+1,rw-lw,c_y,sum_y); } } else if (op[1]=='u'){ scanf(" %c",&to); int l,r; scanf("%d%d%d",&l,&r,&w); if (to=='P'){ update(l,w,c_p,sum_p); update(r+1,-w,c_p,sum_p); }else { update(l,w,c_y,sum_y); update(r+1,-w,c_y,sum_y); } }else if (op[1]=='t'){ scanf(" %c",&to); scanf("%d%d",&x,&y); if (to=='P'){ w=sum(x,c_y,sum_y)-sum(x-1,c_y,sum_y); update(x,-w,c_y,sum_y); update(x+1,w,c_y,sum_y); update(y,w,c_p,sum_p); update(y+1,-w,c_p,sum_p); }else { w=sum(x,c_p,sum_p)-sum(x-1,c_p,sum_p); update(x,-w,c_p,sum_p); update(x+1,w,c_p,sum_p); update(y,w,c_y,sum_y); update(y+1,-w,c_y,sum_y); } }else { int l,r; scanf("%d%d",&l,&r); LL num_p=sum(r,c_p,sum_p)-sum(l-1,c_p,sum_p); LL num_y=sum(r,c_y,sum_y)-sum(l-1,c_y,sum_y); if (num_p>num_y){ cnt1++; printf("P %lld ",num_p); }else { cnt2++; printf("Y %lld ",num_y); } } } if (cnt1>cnt2){ printf("little P is winner! "); }else if (cnt1<cnt2){ printf("little Y is winner! "); }else { printf("five five open "); } } return 0; }
线段树版本：。。。更新laze标记，以及sum的时候，一定要用+=，不要用=，因为往下更新的时候，有可能不为0。
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #define LL long long using namespace std; struct node{ int l,r; LL laze; LL sum; }tree[2][200005<<2]; int a[200005]; int b[200005]; int cnt1; int cnt2; inline int L(int r){return r<<1;}; inline int R(int r){return r<<1|1;}; inline int MID(int l,int r){return (l+r)>>1;}; void push_down(int root,node tre[]){ if (tre[root].laze){ tre[L(root)].laze+=tre[root].laze; tre[R(root)].laze+=tre[root].laze; tre[L(root)].sum+=(LL)tre[root].laze*(tre[L(root)].r-tre[L(root)].l+1); tre[R(root)].sum+=(LL)tre[root].laze*(tre[R(root)].r-tre[R(root)].l+1); tre[root].laze=0; } } void build(int root,int l,int r){ tree[0][root].l=l; tree[1][root].l=l; tree[0][root].r=r; tree[1][root].r=r; tree[0][root].laze=0; tree[1][root].laze=0; tree[0][root].sum=0; tree[1][root].sum=0; if (l==r){ tree[0][root].sum=a[l]; tree[1][root].sum=b[l]; return; } int mid=MID(l,r); build(L(root),l,mid); build(R(root),mid+1,r); tree[0][root].sum=tree[0][L(root)].sum+tree[0][R(root)].sum; tree[1][root].sum=tree[1][L(root)].sum+tree[1][R(root)].sum; } void update(int root,int ul,int ur,LL w,node tre[]){ int l=tre[root].l; int r=tre[root].r; // cout<<l<<" "<<r<<endl; if (ul<=l && r<=ur){ tre[root].sum+=(LL)(r-l+1)*w; tre[root].laze+=w; return; } push_down(root,tre); int mid=MID(l,r); if (ur<=mid) update(L(root),ul,ur,w,tre); else if (ul>mid) update(R(root),ul,ur,w,tre); else { update(L(root),ul,mid,w,tre); update(R(root),mid+1,ur,w,tre); } tre[root].sum=tre[L(root)].sum+tre[R(root)].sum; } LL query(int root,int ql,int qr,node tre[]){ int l=tre[root].l; int r=tre[root].r; if (ql<=l && r<=qr){ return tre[root].sum; } push_down(root,tre); int mid=MID(l,r); LL ans=0; if (qr<=mid){ ans+=query(L(root),ql,qr,tre); }else if (ql>mid){ ans+=query(R(root),ql,qr,tre); }else { ans+=query(L(root),ql,mid,tre); ans+=query(R(root),mid+1,qr,tre); } return ans; } int main(){ int n,m; while(~scanf("%d%d",&n,&m)){ for (int i=1;i<=n;i++){ scanf("%d",&a[i]); } for (int i=1;i<=n;i++){ scanf("%d",&b[i]); } build(1,1,n); cnt1=0; cnt2=0; while(m--){ char op[10]; char pe; int x,y; LL w; scanf("%s",op); if (op[1]=='i'){ scanf(" %c",&pe); if(pe=='P'){ scanf("%d%d",&x,&y); LL lw=query(1,x,x,tree[0]); LL rw=query(1,y,y,tree[0]); update(1,x,x,rw-lw,tree[0]); update(1,y,y,lw-rw,tree[0]); }else { scanf("%d%d",&x,&y); int lw=query(1,x,x,tree[1]); int rw=query(1,y,y,tree[1]); update(1,x,x,rw-lw,tree[1]); update(1,y,y,lw-rw,tree[1]); } }else if (op[1]=='u'){ scanf(" %c",&pe); if (pe=='P'){ scanf("%d%d%lld",&x,&y,&w); update(1,x,y,w,tree[0]); }else { scanf("%d%d%lld",&x,&y,&w); update(1,x,y,w,tree[1]); } }else if (op[1]=='t'){ scanf(" %c",&pe); scanf("%d%d",&x,&y); if (pe=='P'){ w=query(1,x,x,tree[1]); //cout<<w<<endl; update(1,x,x,-w,tree[1]); update(1,y,y,w,tree[0]); // for (int i=1;i<=n;i++){ // cout<<query(1,i,i,tree[0])<<" "; // } // cout<<endl; // for (int i=1;i<=n;i++){ // cout<<query(1,i,i,tree[1])<<" "; // } // cout<<endl; }else { w=query(1,x,x,tree[0]); update(1,x,x,-w,tree[0]); update(1,y,y,w,tree[1]); } }else { scanf("%d%d",&x,&y); LL sum1=query(1,x,y,tree[0]); LL sum2=query(1,x,y,tree[1]); if (sum1>sum2){ printf("P %lld ",sum1); cnt1++; }else { printf("Y %lld ",sum2); cnt2++; } } } if (cnt1>cnt2){ printf("little P is winner! "); }else if (cnt1<cnt2){ printf("little Y is winner! "); }else{ printf("five five open "); } } return 0; } /* 5 5 1 3 2 5 1 1 3 2 5 1 mig Y 3 2 */