给出长度为n的字符串,m个操作。
每个操作有三个值 l,r,op。
op==1,表示将字符串中[ l ,r ]的部分按照升序排列。
op==0,表示将字符串中[ l ,r ]的部分按照降序排列。
输出最终的字符串
按小写字母建26颗线段树
对于每次修改,先记录[l,r]区间内各个字母出现的次数,并对相应区间清空,然后按照升序或者降序从新更新
#include "stdio.h" #include "string.h" char str[100010]; int n,temp; struct node { int l,r,x,lazy; }data[30][400010]; void build(int l,int r,int k,int op) { int mid; data[op][k].l=l; data[op][k].r=r; data[op][k].x=0; data[op][k].lazy=-1; if (l==r) return ; mid=(l+r)/2; build(l,mid,k*2,op); build(mid+1,r,k*2+1,op); } void Pushdown(int k,int op) { if (data[op][k].lazy==-1) return ; if (data[op][k].l==data[op][k].r) return ; if (data[op][k].lazy==0) { data[op][k*2].x=data[op][k*2].lazy=0; data[op][k*2+1].x=data[op][k*2+1].lazy=0; } else { data[op][k*2].x=data[op][k*2].r-data[op][k*2].l+1; data[op][k*2+1].x=data[op][k*2+1].r-data[op][k*2+1].l+1; data[op][k*2].lazy=data[op][k*2+1].lazy=1; } data[op][k].lazy=-1; } void updata(int l,int r,int k,int op) { int mid; if (data[op][k].l==l && data[op][k].r==r) { data[op][k].x=data[op][k].r-data[op][k].l+1; data[op][k].lazy=1; return; } Pushdown(k,op); mid=(data[op][k].l+data[op][k].r)/2; if (r<=mid) updata(l,r,k*2,op); else if (l>mid) updata(l,r,k*2+1,op); else { updata(l,mid,k*2,op); updata(mid+1,r,k*2+1,op); } data[op][k].x=data[op][k*2].x+data[op][k*2+1].x; } void search(int l,int r,int k,int op) { int mid; if (data[op][k].l==l && data[op][k].r==r) { temp+=data[op][k].x; data[op][k].x=0; data[op][k].lazy=0; return ; } Pushdown(k,op); mid=(data[op][k].l+data[op][k].r)/2; if (r<=mid) search(l,r,k*2,op); else if (l>mid) search(l,r,k*2+1,op); else { search(l,mid,k*2,op); search(mid+1,r,k*2+1,op); } data[op][k].x=data[op][k*2].x+data[op][k*2+1].x; } void init() { int i; scanf("%s",str); for (i=0;i<26;i++) build(1,n,1,i); for (i=0;i<n;i++) updata(i+1,i+1,1,str[i]-'a'); } int main() { int m,a,b,c,i,j,k; int mark[30]; while (scanf("%d%d",&n,&m)!=EOF) { init(); while (m--) { scanf("%d%d%d",&a,&b,&c); memset(mark,0,sizeof(mark)); for (i=0;i<26;i++) { temp=0; search(a,b,1,i); // 查找区间内i字母出现的次数,并清空 mark[i]+=temp; } if (c==0) { k=a; for (i=25;i>=0;i--) if (mark[i]!=0) { updata(k,k+mark[i]-1,1,i); // 更新区间字母 k+=mark[i]; } } else { k=a; for (i=0;i<26;i++) if (mark[i]!=0) { updata(k,k+mark[i]-1,1,i); k+=mark[i]; } } } for (i=1;i<=n;i++) { for (j=0;j<26;j++) { temp=0; search(i,i,1,j); if (temp!=0) { printf("%c",j+'a'); break; } } } printf("\n"); } return 0; }