Codeforces 240F

CF_240F.cpp

#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#define MAXN 100001
#define MAXST 262144
#define left(i) (i<<1)+1
#define center(l, r) (l+r)>>1
using namespace std;

typedef pair<int, int> pii;
int sts[26][MAXST], n, adds[26][MAXST];

void stupdate(int st[], int add[], int i, int j, int up, int idx=0, int l=0, int r=n-1) {
    int L = left(idx), R = L+1, mid = center(l, r);
    if(add[idx]) {
        st[idx] = add[idx]>0?r-l+1:0;
        if(l!=r) {
            add[L] = add[idx];
            add[R] = add[idx];
        }
        add[idx] = 0;
    }
    if(l>=i and r<=j) {
        st[idx] = up>0?r-l+1:0;
        if(l!=r) {
            add[L] = up;
            add[R] = up;
        }
        return;
    }
    if(l>j or r<i)
        return;
    stupdate(st, add, i, j, up, L, l, mid);
    stupdate(st, add, i, j, up, R, mid+1, r);
    st[idx] = st[L] + st[R];
}

int stq(int st[], int add[], int i, int j, int idx=0, int l=0, int r=n-1) {
    int L = left(idx), R = L+1, mid = center(l, r);
    if(add[idx]) {
        st[idx] = add[idx]>0?r-l+1:0;
        if(l!=r) {
            add[L] = add[idx];
            add[R] = add[idx];
        }
        add[idx] = 0;
    }
    if(l>=i and r<=j)
        return st[idx];
    if(l>j or r<i)
        return 0;
    return stq(st, add, i, j, L, l, mid)+stq(st, add, i, j, R, mid+1, r);
}

vector<pii> toact;

bool poss(int ini, int fin) {
    toact.clear();
    toact.reserve(27);
    int q = fin-ini+1, h;
    bool impares = false;
    pii impar;
    for(int i=0; q and i<26; i++) {
        h = stq(sts[i], adds[i], ini, fin);
        //cerr<<ini<<" "<<fin<<": "<<i<<"; "<<h<<endl;
        if((h%2)==0) {
            if(h) {
                toact.push_back(pii(i, h));
                q -= h;
            }
        }
        else {
            if(impares)
                return false;
            impares = true;
            impar = pii(i, 1);
            toact.push_back(pii(i, h-1));
            q -= h;
        }
    }
    if(impares)
        toact.push_back(impar);
    return true;
}

void modify(int ini, int fin) {
    //cerr<<"# "<<toact.size()<<endl;
    int u, h;
    int i2=ini, f2=fin;
    for(int i=0; i<toact.size(); i++) {
        u = toact[i].first;
        h = toact[i].second;
        //cerr<<"# "<<string(1,'a'+u)<<" "<<h<<": "<<i2<<" "<<f2<<endl;
        if(h!=1) {
            stupdate(sts[u], adds[u], ini, fin, -1);
            if(h) {
                stupdate(sts[u], adds[u], i2, i2+h/2-1, 1);
                stupdate(sts[u], adds[u], f2-h/2+1, f2, 1);
                i2 += h/2;
                f2 -= h/2;
            }
        }
        else
            stupdate(sts[u], adds[u], i2, f2, 1);
    }
    //cerr<<"----"<<endl;
}

int main() {
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    memset(sts, 0, sizeof sts);
    memset(adds, 0, sizeof adds);
    int k;
    string s;
    cin>>n>>k>>s;
    for(int i=0; i<n; i++)
        stupdate(sts[s[i]-'a'], adds[s[i]-'a'], i, i, 1);
    int i, j;
    while(k--) {
        scanf("%d %d", &i, &j);
        i--, j--;
        if(poss(i, j))
            modify(i, j);
    }
    string ans;
    for(int i=0; i<n; i++)
        for(int j=0; j<26; j++)
            if(stq(sts[j], adds[j], i, i)) {
                ans.push_back('a'+j);
                break;
            }
    cout<<ans<<endl;
    return 0;
}