codeforces 240 F. TorCoder (线段树)
题意：给一个仅由小写字母组成的字符串，然后m个操作，每个操作一个区间，要求把区间中排列成字典序最小的回文串，如果不能形成回文串，就忽略该操作。
思路：和上一道线段树优化计数排序的题目很像，几乎是一样的。
同样的，26棵线段树，每种字母对应一棵。
每次统计询问区间中每种字母的个数。
然后先判断是否能形成回文（奇数长度只有一个个数为奇数的，偶数长度不能出现个数为奇数的）
能的话重置区间，然后前后分别覆盖。
注意如果是奇数长度的话，记得先覆盖中间点。
需要注意这道题的输入输出方式不是标准的。。。而是要加文件。。。不然会MLE 1
然而Tle 19….Tle了好久。。。
最后换了种线段树的写法就过了。。。
然而后面这种写法就一定好么。。。。好像也不是。。。
总之是个挺玄学的东西。。。。不管了。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年10月05日 星期三 04时00分51秒
4File Name :code/cf/problem/240F.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <deque>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <bitset>
19#include <bits/stdc++.h>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+1;
34int tree[26][N*4];
35int lazy[26][N*4];
36int n,m;
37char st[N];
38int cnt[26];
39int L,R;
40inline bool scan_d(int &num)
41{
42 char in;bool IsN=false;
43 in=getchar();
44 if(in==EOF) return false;
45 while(in!='-'&&(in<'0'||in>'9')) in=getchar();
46 if(in=='-'){ IsN=true;num=0;}
47 else num=in-'0';
48 while(in=getchar(),in>='0'&&in<='9'){
49 num*=10,num+=in-'0';
50 }
51 if(IsN) num=-num;
52 return true;
53}
54void PushUp(int rt,int id)
55{
56 tree[id][rt] = tree[id][rt<<1] + tree[id][rt<<1|1];
57}
58void PushDown(int l,int r,int rt,int id)
59{
60 if (lazy[id][rt]==-1) return;
61 lazy[id][rt<<1] = lazy[id][rt<<1|1] = lazy[id][rt];
62 if (lazy[id][rt])
63 {
64 int m = (l+r)>>1;
65 tree[id][rt<<1] = m-l+1;
66 tree[id][rt<<1|1] = r-m;
67 }else tree[id][rt<<1] = tree[id][rt<<1|1] = 0 ;
68 lazy[id][rt] = -1;
69}
70void build(int l,int r,int rt)
71{
72 if (l==r)
73 {
74 int id = st[l-1]-'a';
75 tree[id][rt] = 1;
76 lazy[id][rt] = 1;
77 return;
78 }
79 int m = (l+r)>>1;
80 build(lson);
81 build(rson);
82 for ( int i = 0 ; i < 26 ; i++)
83 PushUp(rt,i);
84}
85
86
87void update(int sc,int l,int r,int rt,int id)
88{
89 if (r<L||l>R) return;
90 if (L<=l&&r<=R)
91 {
92 lazy[id][rt] = sc;
93 if (sc) tree[id][rt] = r - l + 1;
94 else tree[id][rt] = 0;
95 return;
96 }
97 int m = (l+r)>>1;
98 PushDown(l,r,rt,id);
99 update(sc,lson,id);
100 update(sc,rson,id);
101 PushUp(rt,id);
102}
103
104
105
106/*
107void update(int L,int R,int sc,int l,int r,int rt,int id)
108{
109 if (L<=l&&r<=R)
110 {
111 lazy[id][rt] = sc;
112 if (sc) tree[id][rt] = r-l+1;
113 else tree[id][rt] = 0;
114 return;
115 }
116 PushDown(l,r,rt,id);
117 int m = (l+r)>>1;
118 if (L<=m) update(L,R,sc,lson,id);
119 if (R>=m+1) update(L,R,sc,rson,id);
120 PushUp(rt,id);
121}
122*/
123
124int query(int l,int r,int rt,int id)
125{
126 if (r<L||l>R) return 0;
127 if (L<=l&&r<=R) return tree[id][rt];
128 int m = (l+r)>>1;
129 PushDown(l,r,rt,id);
130 return query(lson,id) + query(rson,id);
131}
132
133/*
134intquery(int L,int R,int l,int r,int rt,int id)
135{
136 if (L<=l&&r<=R) return tree[id][rt];
137 PushDown(l,r,rt,id);
138 int m = (l+r)>>1;
139 int ret = 0 ;
140 if (L<=m) ret = query(L,R,lson,id);
141 if (R>=m+1) ret = ret + query(L,R,rson,id);
142 return ret;
143}
144*/
145int main()
146{
147 // freopen("code/in.txt","r",stdin);
148 freopen("input.txt","r",stdin);
149 freopen("output.txt","w",stdout);
150 ms(tree,0);
151 ms(lazy,-1);
152 cin>>n>>m;
153 cin>>st;
154 build(1,n,1);
155 while (m--)
156 {
157 int l,r;
158 // scanf("%d%d",&l,&r);
159 scan_d(l);scan_d(r);
160 // cin>>l>>r;
161 int odd = 0;
162 int even = 0;
163 int InMid=-1;
164 for ( int i = 0 ; i < 26 ; i++)
165 {
166 L = l;
167 R = r;
168 cnt[i] = query(1,n,1,i);
169 if (cnt[i]&1==1) odd++,InMid = i;
170 else even++;
171 if (odd>1) break;
172 }
173 int len = r-l+1;
174 if (len%2==0)
175 {
176 if (odd) continue;
177 }
178 else
179 {
180 if (odd>1) continue;
181 }
182 if (odd==1&&even==0) continue;
183 //先判断能否回文，再打上重置标记。
184 for ( int i = 0 ; i < 26 ; i++)
185 {
186 L = l;
187 R = r;
188 update(0,1,n,1,i);
189 }
190 int fpos = l;
191 int bpos = r;
192 L = (l+r)/2;
193 R = (l+r)/2;
194 if (len%2==1) update(1,1,n,1,InMid);
195 for ( int i = 0 ; i < 26 ; i++)
196 {
197 if (cnt[i]<=1) continue;
198 L = fpos;
199 R = fpos + (cnt[i]>>1)-1;
200// if (L<l||R>(l+r)/2) return 0;
201 update(1,1,n,1,i);
202 L = bpos - (cnt[i]>>1) + 1;
203 R = bpos;
204// if (L<=(l+r)/2||R>r) return 0;
205 update(1,1,n,1,i);
206 fpos +=cnt[i]>>1;
207 bpos-=cnt[i]>>1;
208 }
209 }
210 for ( int i = 1 ; i <= n ; i++)
211 for ( int j = 0 ; j < 26 ; j++)
212 {
213 L = i;
214 R = i;
215 if (query(1,n,1,j))
216 {
217 printf("%c",j+'a');
218 // cout<<char(j+'a');
219 break;
220 }
221 }
222 #ifndef ONLINE_JUDGE
223 fclose(stdin);
224 #endif
225 return 0;
226}