| 1234567 |
- #include <cstdint>
- #include <iostream>
- #include <random>
- #include <string>
- #include <vector>
- using namespace std;struct Node{int l=0,r=0,size=1;char value=0;uint32_t priority=0;};
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,q;string s;cin>>n>>q>>s;mt19937 rng(998244353);vector<Node>tr(1);auto size=[&](int x){return x?tr[x].size:0;};auto pull=[&](int x){tr[x].size=size(tr[x].l)+size(tr[x].r)+1;};auto split=[&](auto&&self,int root,int k)->pair<int,int>{if(!root)return{0,0};if(size(tr[root].l)>=k){auto[a,b]=self(self,tr[root].l,k);tr[root].l=b;pull(root);return{a,root};}auto[a,b]=self(self,tr[root].r,k-size(tr[root].l)-1);tr[root].r=a;pull(root);return{root,b};};auto merge=[&](auto&&self,int a,int b)->int{if(!a||!b)return a?a:b;if(tr[a].priority<tr[b].priority){tr[a].r=self(self,tr[a].r,b);pull(a);return a;}tr[b].l=self(self,a,tr[b].l);pull(b);return b;};int root=0;for(char c:s){int z=tr.size();tr.push_back({0,0,1,c,static_cast<uint32_t>(rng())});root=merge(merge,root,z);}while(q--){int l,r;cin>>l>>r;auto[ab,c]=split(split,root,r);auto[a,b]=split(split,ab,l-1);root=merge(merge,merge(merge,a,c),b);}auto output=[&](auto&&self,int u)->void{if(!u)return;self(self,tr[u].l);cout<<tr[u].value;self(self,tr[u].r);};output(output,root);cout<<'\n';}
|
