TLE on #19

#include <bits/stdc++.h>
using namespace std;
int n,q;
string s;
int sum[30];
const int N=1e5+5;

struct node{
	int sum,lt;
}tr[N*26*4];
int rt[30],cnt,lc[N*26*4],rc[N*26*4];
void build(int &p,int l,int r,int k){
	p=++cnt;
	tr[p].lt=-1;
	if(l==r){
		if(s[l]==char('a'+k)){
			tr[p].sum=1;
		}
		return ;
	}
	int m=l+r>>1;
	build(lc[p],l,m,k);
	build(rc[p],m+1,r,k);
	tr[p].sum=tr[lc[p]].sum+tr[rc[p]].sum;
}

inline void pushdown(int p,int l,int r){
	if(tr[p].lt==-1) return ;
	int m=l+r>>1;
	tr[lc[p]].sum=(m-l+1)*tr[p].lt;
	tr[rc[p]].sum=(r-m)*tr[p].lt;
	tr[lc[p]].lt=tr[p].lt;
	tr[rc[p]].lt=tr[p].lt;
	tr[p].lt=-1;
}
void upd(int p,int l,int r,int ul,int ur,int k){
	if(ul<=l&&r<=ur){
		tr[p].sum=(r-l+1)*k;
		tr[p].lt=k;
		return ;
	}
	pushdown(p,l,r);
	int m=l+r>>1;
	if(m>=ul) upd(lc[p],l,m,ul,ur,k);
	if(m+1<=ur) upd(rc[p],m+1,r,ul,ur,k);
	tr[p].sum=tr[lc[p]].sum+tr[rc[p]].sum;
}
int query(int p,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return tr[p].sum;
	pushdown(p,l,r);
	int m=l+r>>1,ans=0;
	if(m>=ql) ans=query(lc[p],l,m,ql,qr);
	if(m+1<=qr) ans+=query(rc[p],m+1,r,ql,qr);
	return ans;
}

int main(){
	#ifdef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
	cin>>n>>q;
	cin>>s;
	s=' '+s;
	for(int i=0;i<26;i++){
		build(rt[i],1,n,i);
	}
	int l,r,cnt1; 
		int odd;
	while(q--){
		scanf("%d%d",&l,&r);
		cnt1=0;
		for(int i=0;i<26;i++){
			sum[i]=query(rt[i],1,n,l,r);
			if(sum[i]%2==1) cnt1++,odd=i;
		}
		if(cnt1>=2) continue;
		if(cnt1==1){
			if((r-l+1)%2==0) continue;
		}
		for(int i=0;i<26;i++){
			upd(rt[i],1,n,l,r,0);
		}
		if(cnt1==1){
			upd(rt[odd],1,n,(r+l)/2,(r+l)/2,1);
			sum[odd]--;
		}
		
		int L=l,R=r;
		for(int i=0;i<26;i++){
			if(sum[i]){
				//cout<<i<<' '<<L<<' '<<L+sum[i]/2-1<<endl;
				//cout<<i<<' '<<R-sum[i]/2+1<<' '<<R<<endl; 
				upd(rt[i],1,n,L,L+sum[i]/2-1,1);
				upd(rt[i],1,n,R-sum[i]/2+1,R,1);
				L+=sum[i]/2;
				R-=sum[i]/2;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<26;j++){
			if(query(rt[j],1,n,i,i)==1){
			    printf("%c",char('a'+j));
				break;
			}
		}
	}
	return 0;
}