线段树做法求调
查看原帖
线段树做法求调
398310
hundunqidian楼主2023/6/6 18:41

57行代码修改后出错(已在代码中标注)

#include<bits/stdc++.h>
using namespace std;
inline int rd(){
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int const X=1e5+100;
string s;
int n,q,a[X];
struct node{
    int cnt[30],tag,lson,rson;
};
node t[X<<2],mem;
//mem:清零结构体 
int List[30];
inline ls(int rt){
    return rt<<1;
}
inline rs(int rt){
    return rt<<1 | 1;
}
void pushup(int rt){
    for(int i=1;i<=26;i++){
        t[rt].cnt[i]=t[ls(rt)].cnt[i]+t[rs(rt)].cnt[i];
    }
    return ;
}
void build(int rt,int L,int R){
    t[rt]=mem;
    t[rt].lson=L; t[rt].rson=R;
    if(L==R){
        t[rt].cnt[a[L]]=1;
        return; 
    }
    int mid=(L+R)>>1;
    build(ls(rt),L,mid);
    build(rs(rt),mid+1,R);
    pushup(rt);
    return ;
}
void pushdown(int rt){
    if(!t[rt].tag) return ;
    int tmp=t[rt].tag;
    for(int i=1;i<=26;i++){
        t[ls(rt)].cnt[i]=0;
        t[rs(rt)].cnt[i]=0;
    }
    t[ls(rt)].tag=t[rs(rt)].tag=t[rt].tag;
    t[ls(rt)].cnt[tmp]=t[ls(rt)].rson-t[ls(rt)].lson+1;
    t[rs(rt)].cnt[tmp]=t[rs(rt)].rson-t[rs(rt)].lson+1;
    t[rt].tag=0;
    return ;
}
void update(int rt,int L,int R,int uL,int uR,int to){
    if(uL<=L && R<=uR){//本来这行错写为if(L==R),能通过样例与前7个测试点,报错为TLE#8,但修改后无法通过样例
        for(int i=1;i<=26;i++){
            t[rt].cnt[i]=0;
        }
        t[rt].cnt[to]=R-L+1; t[rt].tag=to;
        //cout<<rt<<' '<<to<<'\t';
        return ;
    }
    int mid=(L+R)>>1;
    pushdown(rt);
    if(uL<=mid) update(ls(rt),L,mid,uL,uR,to);
    if(mid+1<=uR) update(rs(rt),mid+1,R,uL,uR,to);
    pushup(rt);
    return ;
}
void query(int rt,int L,int R,int uL,int uR){
    if(uL<=L && R<=uR){
        for(int i=1;i<=26;i++){
            List[i]+=t[rt].cnt[i];
        }
        return;
    }
    int mid=(L+R)>>1;
    pushdown(rt);
    if(uL<=mid) query(ls(rt),L,mid,uL,uR);
    if(mid+1<=uR) query(rs(rt),mid+1,R,uL,uR);
    return ;
}
void out(int rt,int L,int R){
    if(L==R){
        for(int i=1;i<=26;i++){
            if(t[rt].cnt[i]==1){
                putchar('a'+i-1);
                return ;
            } 
        }
        return; 
    }
    int mid=(L+R)>>1;
    out(ls(rt),L,mid);
    out(rs(rt),mid+1,R);
    return ;
}
int main() {
    n=rd(); q=rd(); 
    for(int i=0;i<n;i++){
        a[i+1]=getchar()-97+1;
    }

    for(int i=0;i<30;i++) mem.cnt[i]=0;
    mem.tag=mem.lson=mem.rson=0;

    build(1,1,n);
    while(q--){
        int l,r,k,pos;
        l=rd(); r=rd(); k=rd();
        pos=l;
        memset(List,0,sizeof(List));
        query(1,1,n,l,r);
        if(k==1){
            for(int i=1;i<=26;i++){
                if(List[i]==0) continue;
                update(1,1,n,pos,pos+List[i]-1,i);
                pos+=List[i];
            }
        }
        else{
            for(int i=26;i>=1;i--){
                if(List[i]==0) continue;
                update(1,1,n,pos,pos+List[i]-1,i);
                pos+=List[i];
            }
        }
    }
    out(1,1,n);
    return 0;
}

感谢.JPG

2023/6/6 18:41
加载中...