CF 240F TorCoder(线段树)
题意：给出一个字符串，有m次操作，每次给出一个区间，把区间重新调整成一个回文序列，如果有多种操作，选择字典序最小的。如果不能操作则不操作。最后输出最终的字符串刚入手，感觉好神奇的题，其实要自己多思考。想一下，其实还是很简单的。
首先我们统计一下区间内各个字母的数量，然后比较区间长度的奇偶性，就知道是否 可以操作。
面对于回文串的字典序最小，显然是确定，只需要从小到大枚举26个字母就行了。
所以做法是：线段树统计区间内各个字母的数量
然后根据区间长度的奇偶性，判断是否可以操作。
如果可以操作，就进行对称的区间更新。
注意个细节：对于如果是区间长度是奇数的，那么肯定有且只有一种字母的个数是奇数，那么肯定这个字母位于中间，然后其它字母还是按照字母顺序，两边更新。
大概的每次更新的复杂度是大概查询是26*lgn,然后更新是26*lgn，大概跑了2.5s
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#define mem(a,b) memset(a,b,sizeof(a))
#define N 100005
#define lson step<<1
#define rson step<<1|1
using namespace std;
struct Seg_tree{
int left,right;
int cnt[26],lazy;
}L[N<<2];
int n,m;
char str[N];
int cnt[26];
void push_up(int step){
for(int i=0;i<26;i++)
L[step].cnt[i]=L[lson].cnt[i]+L[rson].cnt[i];
}
void update(int step,int l,int r,int k);
void push_down(int step){
if(L[step].lazy!=-1){
int l=L[step].left,r=L[step].right,m=(l+r)>>1;
update(lson,l,m,L[step].lazy);
update(rson,m+1,r,L[step].lazy);
L[step].lazy=-1;
}
}
void bulid(int step,int l,int r){
L[step].left=l;
L[step].right=r;
L[step].lazy=-1;
mem(L[step].cnt,0);
if(l==r){
L[step].cnt[str[l]-'a']++;
L[step].lazy=str[l]-'a';
return ;
}
int m=(l+r)>>1;
bulid(lson,l,m);
bulid(rson,m+1,r);
push_up(step);
}
void query(int step,int l,int r){
if(L[step].left==l&&L[step].right==r){
for(int i=0;i<26;i++)
cnt[i]+=L[step].cnt[i];
return ;
}
int m=(L[step].left+L[step].right)>>1;
push_down(step);
if(r<=m) query(lson,l,r);
else if(l>m) query(rson,l,r);
else {
query(lson,l,m);
query(rson,m+1,r);
}
}
void update(int step,int l,int r,int k){
if(L[step].left==l&&L[step].right==r){
mem(L[step].cnt,0);
L[step].cnt[k]=r-l+1;
L[step].lazy=k;
return ;
}
push_down(step);
int m=(L[step].left+L[step].right)>>1;
if(r<=m) update(lson,l,r,k);
else if(l>m) update(rson,l,r,k);
else {
update(lson,l,m,k);
update(rson,m+1,r,k);
}
push_up(step);
}
void slove(int step){
if(L[step].left==L[step].right){
putchar(L[step].lazy+'a');
return ;
}
push_down(step);
slove(lson);
slove(rson);
}
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d%d%s",&n,&m,str+1);
bulid(1,1,n);
while(m--){
int l,r;
scanf("%d%d",&l,&r);
mem(cnt,0);
query(1,l,r);
if((r-l+1)&1){
int k=0,p;
for(int i=0;i<26;i++)
if(cnt[i]&1) k++,p=i;
if(k==1){
int a=l,b=r;
cnt[p]--;
for(int i=0;i<26;i++){
if(cnt[i]){
update(1,a,a+cnt[i]/2-1,i);
update(1,b-cnt[i]/2+1,b,i);
a+=cnt[i]/2;
b-=cnt[i]/2;
}
}
update(1,a,b,p);
}
}
else{
int k=0;
for(int i=0;i<26;i++)
if(cnt[i]&1){
k=1;
break;
补充：软件开发 , C++ ,
- 更多C/C++疑问解答：
- 关于c++的cout输出的问题。
- 在学校里学过C和C++，不过学的很一般，现在自学C#，会不会很难？
- 全国计算机二级C语言笔试题
- 已知某树有2个2度结点，3个3度结点，4个4度结点，问有几个叶子结点？
- c++数据结构内部排序问题，整数排序
- 2012九月计算机二级C语言全国题库，，急求急求
- 如果assert只有一个字符串作为参数，是什么意思呢?
- C语言中，哪些运算符具有左结合性，哪些具有右结合性，帮忙总结下，谢谢了！
- 为什么用结构体编写的程序输入是，0输不出来啊~~~
- 将IEEE—754的十六进制转化为十进制浮点类型，用C或C++都行，多谢各位大侠啊，非常感谢！
- 为什么这个程序求不出公式？
- 这个链表倒置的算法请大家分析下
- c语言函数库调用
- C语言unsigned int纠错
- C语言快排求解啊