codeforces 240 F. TorCoder (线段树)

Posted by 111qqz on Wednesday, October 5, 2016

TOC

题目链接

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

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

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

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

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

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

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

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

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

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

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

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

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

/* ***********************************************
Author :111qqz
Created Time :2016年10月05日 星期三 04时00分51秒
File Name :code/cf/problem/240F.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <deque>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <bitset>
#include <bits/stdc++.h>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+1;
int tree[26][N*4];
int lazy[26][N*4];
int n,m;
char st[N];
int cnt[26];
int L,R;
inline bool scan_d(int &num)  
{
        char in;bool IsN=false;
        in=getchar();
        if(in==EOF) return false;
        while(in!='-'&&(in<'0'||in>'9')) in=getchar();
        if(in=='-'){ IsN=true;num=0;}
        else num=in-'0';
        while(in=getchar(),in>='0'&&in<='9'){
                num*=10,num+=in-'0';
        }
        if(IsN) num=-num;
        return true;
}
void PushUp(int rt,int id)
{
    tree[id][rt] = tree[id][rt<<1] + tree[id][rt<<1|1];
}
void PushDown(int l,int r,int rt,int id)
{
    if (lazy[id][rt]==-1) return;
    lazy[id][rt<<1] = lazy[id][rt<<1|1] = lazy[id][rt];
    if (lazy[id][rt])
    {
    int m = (l+r)>>1;
    tree[id][rt<<1] = m-l+1;
    tree[id][rt<<1|1] = r-m;
    }else tree[id][rt<<1] = tree[id][rt<<1|1] = 0 ;
    lazy[id][rt] = -1;
}
void build(int l,int r,int rt)
{
    if (l==r)
    {
    int id = st[l-1]-'a';
    tree[id][rt] = 1;
    lazy[id][rt] = 1;
    return;
    }
    int m = (l+r)>>1;
    build(lson);
    build(rson);
    for ( int i = 0 ; i < 26 ; i++)
    PushUp(rt,i);
}


void update(int sc,int l,int r,int rt,int id)
{
    if (r<L||l>R) return;
    if (L<=l&&r<=R)
    {
    lazy[id][rt] = sc;
    if (sc) tree[id][rt] =  r - l + 1;
    else tree[id][rt] = 0;
    return;
    }
    int m = (l+r)>>1;
    PushDown(l,r,rt,id);
    update(sc,lson,id);
    update(sc,rson,id);
    PushUp(rt,id);
}



/*
void update(int L,int R,int sc,int l,int r,int rt,int id)
{
    if (L<=l&&r<=R)
    {
    lazy[id][rt] = sc;
    if (sc) tree[id][rt] = r-l+1;
    else tree[id][rt] =  0;
    return;
    }
    PushDown(l,r,rt,id);
    int m = (l+r)>>1;
    if (L<=m) update(L,R,sc,lson,id);
    if (R>=m+1) update(L,R,sc,rson,id);
    PushUp(rt,id);
}
*/

int query(int l,int r,int rt,int id)
{
    if (r<L||l>R) return 0;
    if (L<=l&&r<=R) return tree[id][rt];
    int m = (l+r)>>1;
    PushDown(l,r,rt,id);
    return query(lson,id) + query(rson,id);
}

/*
intquery(int L,int R,int l,int r,int rt,int id)
{
    if (L<=l&&r<=R) return tree[id][rt];
    PushDown(l,r,rt,id);
    int m = (l+r)>>1;
    int ret = 0 ;
    if (L<=m) ret = query(L,R,lson,id);
    if (R>=m+1) ret = ret + query(L,R,rson,id);
    return ret;
}
*/
int main()
{
  //     freopen("code/in.txt","r",stdin);
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    ms(tree,0);
    ms(lazy,-1);
    cin>>n>>m;
    cin>>st;
    build(1,n,1);
    while (m--)
    {
        int l,r;
       // scanf("%d%d",&l,&r);
        scan_d(l);scan_d(r);
       // cin>>l>>r;
        int odd = 0;
        int even = 0;
        int InMid=-1;
        for ( int i = 0 ; i < 26 ; i++)
        {
        L = l;
        R = r;
        cnt[i] = query(1,n,1,i);
        if (cnt[i]&1==1) odd++,InMid = i;
        else even++;
        if (odd>1) break;
        }
        int len = r-l+1;
        if (len%2==0)
        {
        if (odd) continue;
        }
        else
        {
        if (odd>1) continue;
        }
        if (odd==1&&even==0) continue;
        //先判断能否回文,再打上重置标记。
        for ( int i = 0 ; i < 26 ; i++)
        {
        L = l;
        R = r;
        update(0,1,n,1,i);
        }
        int fpos = l;
        int bpos = r;
        L = (l+r)/2;
        R = (l+r)/2;
        if (len%2==1) update(1,1,n,1,InMid);
        for ( int i = 0 ; i < 26 ; i++)
        {
        if (cnt[i]<=1) continue;
        L = fpos;
        R = fpos + (cnt[i]>>1)-1;
//		if (L<l||R>(l+r)/2) return 0;
        update(1,1,n,1,i);
        L = bpos - (cnt[i]>>1) + 1;
        R = bpos;
//		if (L<=(l+r)/2||R>r) return 0;
        update(1,1,n,1,i);
        fpos +=cnt[i]>>1;
        bpos-=cnt[i]>>1;
        }
    }
    for ( int i = 1 ; i <= n ; i++)
        for ( int j = 0 ; j < 26 ; j++)
        {
        L = i;
        R = i;
        if (query(1,n,1,j))
        {
            printf("%c",j+'a');
         //   cout<<char(j+'a');
            break;
        }
        }
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付