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