正解炸了……
考试的时候想到了正解，非常高兴的打出来了线段树，又调了好长时间，对拍了一下发现除了非常大的点跑的有点慢外其他还行。因为复杂度算着有点高……
最后正解死于常数太大……旁边的lyl用同样的算法拿了90分我却拿了个暴力的分40……花了那么多时间一分没多拿原地爆炸……
由于大部分时间押在了T1，然后考试就炸了……
题解：
因为字符串长度虽然很大，但是只有26个字符，考虑桶排，用线段树每个节点开一个26的桶，维护这个区间中各个数的个数，对于排序就可以拆成26次区间赋值。然而这样的down函数的复杂度是26，于是整个算法的复杂度就成了$nlog_n*26^2$,40分成功炸掉（加两个优化可以搞到60分），然后就有lyl及其没有素质地给他循环展开了,AC……
还是说正解吧，和‘花神游历各国’类似，线段树维护这一段的值，不一样则为0，本来以为这样会很慢，但是它会越来越快：每次排序最多增加2个块，但这种增加是有限制的，大部分情况下块是在减少，所以它会越来越快。由于此时的down是O1的，于是总复杂度$nlog_n*26$，成功A掉。
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #define MAXN 100010
5 using namespace std;
6 struct tree
7 {
8 int l,r,sum;
9 #define l(x) tr[x].l
10 #define r(x) tr[x].r
11 #define ls(x) (x*2)
12 #define rs(x) ((ls(x))+1)
13 #define sum(x) tr[x].sum
14 }tr[MAXN*100];
15 char a[MAXN];
16 int n,m,yz[MAXN];
17 void pushup(int x)
18 {
19 if(l(x)==r(x))return;
20 sum(x)=(sum(ls(x))==sum(rs(x))?sum(ls(x)):0);
21 }
22 void build(int l,int r,int x)
23 {
24 l(x)=l,r(x)=r;
25 if(l==r){sum(x)=a[l];yz[l]=x;return;}
26 int mid=(l+r)>>1;
27 build(l,mid,ls(x));
28 build(mid+1,r,rs(x));
29 pushup(x);
30 }
31 void down(int x)
32 {
33 if(!sum(x))return;
34 if(l(x)!=r(x))sum(ls(x))=sum(rs(x))=sum(x);
35 }
36 void add(int l,int r,int x,int data)
37 {
38 if((l(x)>=l&&r(x)<=r)||sum(x)==data)
39 {sum(x)=data;down(x);return;}
40 down(x);
41 int mid=(l(x)+r(x))>>1;
42 if(l<=mid)add(l,r,ls(x),data);
43 if(r>mid) add(l,r,rs(x),data);
44 pushup(x);
45 }
46 int t[27];
47 void ask(int l,int r,int x)
48 {
49 down(x);
50 if(l>r(x)||r<l(x))return;
51 if(l<=l(x)&&r>=r(x)&&sum(x))
52 {
53 t[sum(x)]+=r(x)-l(x)+1;
54 return;
55 }
56 down(x);
57 int mid=(l(x)+r(x))>>1;
58 if(l<=mid)ask(l,r,ls(x));
59 if(r>mid) ask(l,r,rs(x));
60 }
61 void work(int x,int l,int r)
62 {
63 memset(t,0,sizeof(t));
64 ask(l,r,1);
65 int tl=l;
66 if(x==1)
67 {
68 for(register int i=1;i<=26;i++)
69 if(t[i])
70 {
71 add(tl,tl+t[i]-1,1,i);
72 tl=tl+t[i];
73 }
74 }
75 else
76 {
77 for(register int i=26;i>=1;i--)
78 if(t[i])
79 {
80 add(tl,tl+t[i]-1,1,i);
81 tl=tl+t[i];
82 }
83 }
84 }
85 void dfs(int x)
86 {
87 down(x);
88 if(l(x)==r(x))return;
89 dfs(ls(x)),dfs(rs(x));
90 }
91 inline int read();
92 signed main()
93 {
94 // freopen("in.txt","r",stdin) ;
95
96 n=read(),m=read();
97 char ooo=getchar();int len=0;
98 while(ooo<'a'||ooo>'z')ooo=getchar();
99 while(ooo>='a'&&ooo<='z'){a[++len]=ooo-'a'+1;ooo=getchar();}
100 build(1,n,1);
101 int x,l,r;
102 for(register int i=1;i<=m;++i)
103 {
104 l=read(),r=read(),x=read();
105 work(x,l,r);
106 }
107 dfs(1);
108 for(int i=1;i<=n;i++)
109 putchar(sum(yz[i])+'a'-1);
110 puts("");
111 }
112 inline int read()
113 {
114 int s=0;char a=getchar();
115 while(a<'0'||a>'9')a=getchar();
116 while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();}
117 return s;
118 }
View Code