fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<ll,ll> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. typedef struct node
  25. {
  26.     int prior,size;
  27.     int val;//value stored in the array
  28.     int sum;//whatever info you want to maintain in segtree for each node
  29.     int lazy;//whatever lazy update you want to do
  30.     bool rev;
  31.     bool rev_lazy;
  32.     struct node *l,*r;
  33. }node;
  34.  
  35. typedef node* pnode;
  36.  
  37. node buffer[600001];
  38. pnode tr;
  39. pnode null;
  40.  
  41. int sz(pnode t)
  42. {
  43.     return t?t->size:0;
  44. }
  45.  
  46. void upd_sz(pnode t)
  47. {
  48.     if(t)t->size=sz(t->l)+1+sz(t->r);
  49. }
  50.  
  51. void lazy(pnode t)
  52. {
  53.     if(!t)return;
  54.     t->val+=t->lazy;//operation of lazy
  55.     t->sum+=t->lazy*sz(t);
  56.     t->rev^=t->rev_lazy;
  57.     if(t->rev)
  58.     {
  59. 		swap(t->l, t->r);
  60. 		t->rev = 0;
  61. 	}
  62.     if(t->l)
  63.     {
  64. 		t->l->lazy+=t->lazy;//propagate lazy
  65. 		t->l->rev_lazy^=t->rev_lazy;
  66. 	}
  67.     if(t->r)
  68.     {
  69. 		t->r->lazy+=t->lazy;
  70. 		t->r->rev_lazy^=t->rev_lazy;
  71. 	}
  72.     t->lazy=0; t->rev_lazy=0;
  73. }
  74.  
  75. void reset(pnode t)
  76. {
  77.     if(t)
  78.     {
  79. 		t->sum = 0;//no need to reset lazy coz when we call this lazy would itself be propagated
  80. 		t->rev = false;
  81. 	}
  82. }
  83.  
  84. void combine(pnode& t,pnode l,pnode r)
  85. {//combining two ranges of segtree
  86.     if(!l || !r)return void(t = l?l:r);
  87.     t->sum = l->sum + r->sum;
  88. }
  89.  
  90. void operation(pnode t)
  91. {//operation of segtree
  92.     if(!t)return;
  93.     reset(t);//reset the value of current node assuming it now represents a single element of the array
  94.     lazy(t->l);lazy(t->r);//imp:propagate lazy before combining t->l,t->r;
  95.     combine(t,t->l,t);
  96.     combine(t,t,t->r);
  97. }
  98.  
  99. void split(pnode t,pnode &l,pnode &r,int pos,int add=0)
  100. {
  101.     if(!t)return void(l=r=NULL);
  102.     lazy(t);
  103.     int curr_pos = add + sz(t->l);
  104.     if(curr_pos<=pos)//element at pos goes to left subtree(l)
  105.         split(t->r,t->r,r,pos,curr_pos+1),l=t;
  106.     else 
  107.         split(t->l,l,t->l,pos,add),r=t;
  108.     upd_sz(t);
  109.     operation(t);
  110. }
  111.  
  112. void merge(pnode &t,pnode l,pnode r)
  113. { //l->leftarray,r->rightarray,t->resulting array
  114.     lazy(l);lazy(r);
  115.     if(!l || !r) t = l?l:r;
  116.     else if(l->prior>r->prior)merge(l->r,l->r,r),t=l;
  117.     else    merge(r->l,l,r->l),t=r;
  118.     upd_sz(t);
  119.     operation(t);
  120. }
  121.  
  122. node *ptr = buffer;
  123.  
  124. pnode init(int val)
  125. {
  126.     pnode ret = ptr;
  127.     ret->prior=rand();ret->size=1;
  128.     ret->val=val;
  129.     ret->sum=0;ret->lazy=0;
  130.     ret->rev = false;
  131.     ptr++;
  132.     return ret;
  133. }
  134.  
  135. int range_query(pnode t,int l,int r)
  136. {//[l,r]
  137.     pnode L,mid,R;
  138.     split(t,L,mid,l-1);
  139.     split(mid,t,R,r-l);//note: r-l!!
  140.     int ans = (t->sum+t->val)%26;
  141.     //int ans = t->sum;
  142.     merge(mid,L,t);
  143.     merge(t,mid,R);
  144.     return ans;
  145. }
  146.  
  147. void range_update(pnode t,int l,int r,int val)
  148. {//[l,r]
  149.     pnode L,mid,R;
  150.     split(t,L,mid,l-1);
  151.     split(mid,t,R,r-l);//note: r-l!!
  152.     t->lazy+=val; //lazy_update
  153.     merge(mid,L,t);
  154.     merge(t,mid,R);
  155. }
  156.  
  157. void range_reverse(pnode t,int l,int r)
  158. {//[l,r]
  159.     pnode L,mid,R;
  160.     split(t,L,mid,l-1);
  161.     split(mid,t,R,r-l);//note: r-l!!
  162.     t->rev_lazy^=1; //lazy_update
  163.     merge(mid,L,t);
  164.     merge(t,mid,R);
  165. }
  166.  
  167. char cycshift(char c, int x)
  168. {
  169. 	int z = c - 'a';
  170. 	z += x;
  171. 	z%=26;
  172. 	return char(z+'a');
  173. }
  174.  
  175. string s;
  176.  
  177. void initialize(int n)
  178. {
  179. 	tr = NULL;
  180. 	for(int i = 0; i < n; i++)
  181. 	{
  182. 		pnode tmp = init(int(s[i]-'a'));
  183. 	    merge(tr, tr, tmp);
  184. 	}
  185. }
  186.  
  187. void upd(int l, int r, int pos) //split is 0-indexed
  188. {
  189. 	pnode L;
  190. 	pnode R;
  191. 	split(tr, L, R, l-1);
  192. 	pnode mid;
  193. 	split(R, mid, R, r-l);
  194. 	merge(L, L, R);
  195. 	pnode L2;
  196. 	pnode R2;
  197. 	split(L, L2, R2, pos);
  198. 	merge(tr, L2, mid);
  199. 	merge(tr, tr, R2);
  200. }
  201.  
  202. int main()
  203. {
  204. 	ios_base::sync_with_stdio(0); cin.tie(0);
  205. 	srand(123);
  206. 	cin >> s;
  207. 	initialize(int(s.length()));
  208. 	int q; cin >> q;
  209. 	while(q--)
  210. 	{
  211. 		int t, l, r;
  212. 		cin>>t>>l>>r;
  213. 		l--; r--;
  214. 		if(t == 1)
  215. 		{
  216. 			int pos; cin >> pos; pos--;
  217. 			upd(l, r, pos);
  218. 		}
  219. 		else if(t == 2)
  220. 		{
  221. 			int c; cin >> c;
  222. 			c%=26;
  223. 			range_update(tr, l, r, c);
  224. 		}
  225. 		else
  226. 		{
  227. 			range_reverse(tr, l, r);
  228. 		}
  229. 	}
  230. 	for(int i = 0; i < s.length(); i++)
  231. 	{
  232. 		//cerr<<range_query(tr,i,i)<<'\n';
  233. 		s[i] = char('a' + range_query(tr,i,i));
  234. 	}
  235. 	cout << s;
  236. }
  237.  
Runtime error #stdin #stdout 0s 39504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hZHciL
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!