codeforces 240 F. TorCoder (线段树)

题目链接

题意:给一个仅由小写字母组成的字符串,然后m个操作,每个操作一个区间,要求把区间中排列成字典序最小的回文串,如果不能形成回文串,就忽略该操作。

思路:和上一道线段树优化计数排序的题目很像,几乎是一样的。

同样的,26棵线段树,每种字母对应一棵。

每次统计询问区间中每种字母的个数。

然后先判断是否能形成回文(奇数长度只有一个个数为奇数的,偶数长度不能出现个数为奇数的)

能的话重置区间,然后前后分别覆盖。

注意如果是奇数长度的话,记得先覆盖中间点。

需要注意这道题的输入输出方式不是标准的。。。而是要加文件。。。不然会MLE 1

然而Tle 19....Tle了好久。。。

2016-10-05-17-43-28-

最后换了种线段树的写法就过了。。。

然而后面这种写法就一定好么。。。。好像也不是。。。

总之是个挺玄学的东西。。。。不管了。。。

 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}
 1void update(int sc,int l,int r,int rt,int id)
 2{
 3    if (r<L||l>R) return;
 4    if (L<=l&&r<=R)
 5    {
 6	lazy[id][rt] = sc;
 7	if (sc) tree[id][rt] =  r - l + 1;
 8	else tree[id][rt] = 0;
 9	return;
10    }
11    int m = (l+r)>>1;
12    PushDown(l,r,rt,id);
13    update(sc,lson,id);
14    update(sc,rson,id);
15    PushUp(rt,id);
16}
 1/*
 2void update(int L,int R,int sc,int l,int r,int rt,int id)
 3{
 4    if (L<=l&&r<=R)
 5    {
 6	lazy[id][rt] = sc;
 7	if (sc) tree[id][rt] = r-l+1;
 8	else tree[id][rt] =  0;
 9	return;
10    }
11    PushDown(l,r,rt,id);
12    int m = (l+r)>>1;
13    if (L<=m) update(L,R,sc,lson,id);
14    if (R>=m+1) update(L,R,sc,rson,id);
15    PushUp(rt,id);
16}
17*/
1int query(int l,int r,int rt,int id)
2{
3    if (r<L||l>R) return 0;
4    if (L<=l&&r<=R) return tree[id][rt];
5    int m = (l+r)>>1;
6    PushDown(l,r,rt,id);
7    return query(lson,id) + query(rson,id);
8}
 1/*
 2intquery(int L,int R,int l,int r,int rt,int id)
 3{
 4    if (L<=l&&r<=R) return tree[id][rt];
 5    PushDown(l,r,rt,id);
 6    int m = (l+r)>>1;
 7    int ret = 0 ;
 8    if (L<=m) ret = query(L,R,lson,id);
 9    if (R>=m+1) ret = ret + query(L,R,rson,id);
10    return ret;
11}
12*/
13int main()
14{
15  //     freopen("code/in.txt","r",stdin);
16	freopen("input.txt","r",stdin);
17	freopen("output.txt","w",stdout);
18	ms(tree,0);
19	ms(lazy,-1);
20	cin>>n>>m;
21	cin>>st;
22	build(1,n,1);
23	while (m--)
24	{
25	    int l,r;
26	   // scanf("%d%d",&l,&r);
27	    scan_d(l);scan_d(r);
28	   // cin>>l>>r;
29	    int odd = 0;
30	    int even = 0;
31	    int InMid=-1;
32	    for ( int i = 0 ; i < 26 ; i++)
33	    {
34		L = l;
35		R = r;
36		cnt[i] = query(1,n,1,i);
37		if (cnt[i]&1==1) odd++,InMid = i;
38		else even++;
39		if (odd>1) break;
40	    }
41	    int len = r-l+1;
42	    if (len%2==0)
43	    {
44		if (odd) continue;
45	    }
46	    else
47	    {
48		if (odd>1) continue;
49	    }
50	    if (odd==1&&even==0) continue;
51	    //先判断能否回文,再打上重置标记。
52	    for ( int i = 0 ; i < 26 ; i++)
53	    {
54		L = l;
55		R = r;
56		update(0,1,n,1,i);
57	    }
58	    int fpos = l;
59	    int bpos = r;
60	    L = (l+r)/2;
61	    R = (l+r)/2;
62	    if (len%2==1) update(1,1,n,1,InMid);
63	    for ( int i = 0 ; i < 26 ; i++)
64	    {
65		if (cnt[i]<=1) continue;
66		L = fpos;
67		R = fpos + (cnt[i]>>1)-1;
68//		if (L<l||R>(l+r)/2) return 0;
69		update(1,1,n,1,i);
70		L = bpos - (cnt[i]>>1) + 1;
71		R = bpos;
72//		if (L<=(l+r)/2||R>r) return 0;
73		update(1,1,n,1,i);
74		fpos +=cnt[i]>>1;
75		bpos-=cnt[i]>>1;
76	    }
77	}
78	for ( int i = 1 ; i <= n ; i++)
79	    for ( int j = 0 ; j < 26 ; j++)
80	    {
81		L = i;
82		R = i;
83		if (query(1,n,1,j))
84		{
85		    printf("%c",j+'a');
86		 //   cout<<char(j+'a');
87		    break;
88		}
89	    }
90  #ifndef ONLINE_JUDGE  
91  fclose(stdin);
92  #endif
93    return 0;
94}