UESTC 数据结构专题训练 A,B,C

A：题目链接 http://acm.uestc.edu.cn/#/problem/show/1591

解法：RMQ或者线段树

【num of wa】 0



#include <bits/stdc++.h> using namespace std; int n, q, mx[50010][20],mi[50010][20],a[50010]; void RMQ(){ for(int i=1; i<=n; i++) mx[i][0]=mi[i][0]=a[i]; for(int j=1; j<20; j++){ for(int i=1; i<=n; i++){ if((i+(1<<j)-1)<=n){ mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]); mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]); } } } } int query1(int x, int y){ int k = log2(y-x+1); return max(mx[x][k], mx[y-(1<<k)+1][k]); } int query2(int x, int y){ int k = log2(y-x+1); return min(mi[x][k], mi[y-(1<<k)+1][k]); } int main() { while(~scanf("%d %d", &n, &q)){ for(int i=1; i<=n; i++) scanf("%d", &a[i]); RMQ(); while(q--){ int l,r; scanf("%d %d", &l, &r); printf("%d\n", query1(l,r)-query2(l,r)); } } return 0; }

B：题目链接 http://acm.uestc.edu.cn/#/problem/show/1592

解法：普通的线段树区间合并

【num of wa】 2

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
struct node{
    int l,r,len,sum1,lsum1,rsum1,sum2,lsum2,rsum2,cover;
}T[maxn*4];
void pushup(int rt){
    T[rt].lsum1=T[rt<<1].lsum1;
    T[rt].lsum2=T[rt<<1].lsum2;
    if(T[rt<<1].lsum1==T[rt<<1].len) T[rt].lsum1+=T[rt<<1|1].lsum1;
    if(T[rt<<1].lsum2==T[rt<<1].len) T[rt].lsum2+=T[rt<<1|1].lsum2;

    T[rt].rsum1=T[rt<<1|1].rsum1;
    T[rt].rsum2=T[rt<<1|1].rsum2;
    if(T[rt<<1|1].rsum1==T[rt<<1|1].len) T[rt].rsum1+=T[rt<<1].rsum1;
    if(T[rt<<1|1].rsum2==T[rt<<1|1].len) T[rt].rsum2+=T[rt<<1].rsum2;

    T[rt].sum1 = max(max(T[rt<<1].sum1, T[rt<<1|1].sum1), T[rt<<1].rsum1+T[rt<<1|1].lsum1);
    T[rt].sum2 = max(max(T[rt<<1].sum2, T[rt<<1|1].sum2), T[rt<<1].rsum2+T[rt<<1|1].lsum2);
}
void pushdown(int rt){
    if(T[rt].cover){
        T[rt<<1].cover^=1;
        T[rt<<1|1].cover^=1;
        swap(T[rt*2].lsum1, T[rt*2].lsum2);
        swap(T[rt*2].rsum1, T[rt*2].rsum2);
        swap(T[rt*2].sum1, T[rt*2].sum2);

        swap(T[rt*2+1].lsum1, T[rt*2+1].lsum2);
        swap(T[rt*2+1].rsum1, T[rt*2+1].rsum2);
        swap(T[rt*2+1].sum1, T[rt*2+1].sum2);
        T[rt].cover=0;
    }
}
void Build(int l, int r, int rt){
    T[rt].l = l, T[rt].r = r, T[rt].len = r-l+1, T[rt].cover=0;
    if(l==r){
        int x;
        scanf("%d",&x);
        T[rt].lsum1=T[rt].rsum1=T[rt].sum1=x;
        T[rt].lsum2=T[rt].rsum2=T[rt].sum2=!x;
        return;
    }
    int mid=(l+r)/2;
    Build(l,mid,rt*2);
    Build(mid+1,r,rt*2+1);
    pushup(rt);
}
void update(int L, int R, int rt){
    if(L<=T[rt].l&&T[rt].r<=R){
        T[rt].cover^=1;
        swap(T[rt].lsum1, T[rt].lsum2);
        swap(T[rt].rsum1, T[rt].rsum2);
        swap(T[rt].sum1, T[rt].sum2);
        return;
    }
    pushdown(rt);
    int mid=(T[rt].l+T[rt].r)>>1;
    if(R<=mid) update(L,R,rt<<1);
    else if(L>mid) update(L,R,rt<<1|1);
    else{
        update(L,mid,rt<<1);
        update(mid+1,R,rt<<1|1);
    }
    pushup(rt);
}
int query(int L, int R, int rt){
    if(L<=T[rt].l&&T[rt].r<=R){
        return T[rt].sum1;
    }
    pushdown(rt);
    int mid=(T[rt].l+T[rt].r)/2;
    if(R<=mid) return query(L,R,rt<<1);
    else if(L>mid) return query(L,R,rt<<1|1);
    else{
        return max(max(query(L,mid,rt<<1),query(mid+1,R,rt<<1|1)),min(mid-L+1,T[rt<<1].rsum1)+min(T[rt<<1|1].lsum1,R-mid));
    }
}
int main()
{
    int n;
    while(~scanf("%d", &n)){
        Build(1,n,1);
        int q;
        scanf("%d", &q);
        while(q--){
            int K,L,R;
            scanf("%d %d %d", &K, &L, &R);
            if(K==1){
                update(L,R,1);
            }
            else{
                printf("%d\n", query(L,R,1));
            }
        }
    }
    return 0;
}

C：题目链接：http://acm.uestc.edu.cn/#/problem/show/1597

解法：线段树Lazy标记，不过要区分乘和加的优先级。

【num of wa】 5



#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 100010; LL sum[maxn<<2], mul[maxn<<2], add[maxn<<2], mod; void pushup(int rt){ sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mod; } void update(int x, int y, int l, int r, int rt){ mul[rt]=1; add[rt]=0; sum[rt]+=y; if(l==r) return; int mid=(l+r)/2; if(x<=mid) update(x,y,l,mid,rt<<1); else update(x,y,mid+1,r,rt<<1|1); pushup(rt); } void pushdown(int rt, int l, int r, int mid){ if(mul[rt]==1&&add[rt]==0) return; mul[rt<<1]=mul[rt<<1]*mul[rt]%mod; add[rt<<1]=(add[rt<<1]*mul[rt]%mod+add[rt])%mod; sum[rt<<1]=(sum[rt<<1]*mul[rt]%mod+add[rt]*(LL)(mid-l+1)%mod)%mod; mul[rt<<1|1]=mul[rt<<1|1]*mul[rt]%mod; add[rt<<1|1]=(add[rt<<1|1]*mul[rt]%mod+add[rt])%mod; sum[rt<<1|1]=(sum[rt<<1|1]*mul[rt]%mod+add[rt]*(LL)(r-mid)%mod)%mod; mul[rt]=1; add[rt]=0; } void update1(int L, int R, int x, int l, int r, int rt){ if(L<=l&&r<=R){ mul[rt]=mul[rt]*(LL)x%mod; add[rt]=add[rt]*(LL)x%mod; sum[rt]=sum[rt]*(LL)x%mod; return ; } int mid=(l+r)/2; pushdown(rt,l,r,mid); if(R<=mid) update1(L,R,x,l,mid,rt*2); else if(L>mid) update1(L,R,x,mid+1,r,rt*2+1); else{ update1(L,mid,x,l,mid,rt*2); update1(mid+1,R,x,mid+1,r,rt*2+1); } pushup(rt); } void update2(int L, int R, int x, int l, int r, int rt){ if(L<=l&&r<=R){ add[rt]=(add[rt]+(LL)x)%mod; sum[rt]=(sum[rt]+(LL)(R-L+1)*x%mod)%mod; return; } int mid=(l+r)/2; pushdown(rt,l,r,mid); if(R<=mid) update2(L,R,x,l,mid,rt*2); else if(L>mid) update2(L,R,x,mid+1,r,rt*2+1); else{ update2(L,mid,x,l,mid,rt*2); update2(mid+1,R,x,mid+1,r,rt*2+1); } pushup(rt); } LL query(int L, int R, int l, int r, int rt){ if(L<=l&&r<=R){ return sum[rt]%mod; } int mid=(l+r)/2; pushdown(rt,l,r,mid); if(R<=mid) return query(L,R,l,mid,rt<<1)%mod; else if(L>mid) return query(L,R,mid+1,r,rt<<1|1)%mod; else return (query(L,mid,l,mid,rt<<1)+query(mid+1,R,mid+1,r,rt<<1|1))%mod; } int main() { int n,q; while(~scanf("%d%lld",&n,&mod)){ for(int i=1; i<=n; i++){ int x; scanf("%d", &x); update(i,x%mod,1,n,1); } scanf("%d", &q); while(q--){ int op,l,r; scanf("%d %d %d", &op,&l,&r); if(op==3){ printf("%lld\n",query(l,r,1,n,1)%mod); } else if(op==1){ LL x; scanf("%lld",&x); update1(l,r,x,1,n,1); } else{ LL x; scanf("%lld",&x); update2(l,r,x,1,n,1); } } } }