Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* CPP Tempelate
- * @author Devashish Tyagi
- */
- #include <algorithm>
- #include <cctype>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <iostream>
- #include <map>
- #include <queue>
- #include <set>
- #include <sstream>
- #include <stack>
- #include <string>
- #include <vector>
- using namespace std;
- typedef long long ll;
- struct Node{
- char upd;
- // 0 - Buccaneer pirates
- // 1 - Barbary pirates
- int p[2];
- Node(){
- p[0] = 0;
- p[1] = 0;
- upd = ' ';
- }
- void update(char cmd){
- if (cmd == 'I'){
- switch(upd){
- case ' ': upd = 'I';break;
- case 'I': upd = ' ';break;
- case 'E': upd = 'F';break;
- case 'F': upd = 'E';break;
- }
- }
- else if (cmd != ' '){
- upd = cmd;
- }
- }
- void S(){
- int temp;
- switch(upd){
- case 'I': temp=p[0]; p[0]=p[1]; p[1]=temp; break;
- case 'E': p[1]+=p[0]; p[0]=0; break;
- case 'F': p[0]+=p[1]; p[1]=0; break;
- }
- upd = ' ';
- }
- };
- Node tree[4028000];
- char pirates[1024010];
- void buildTree(int index, int i, int j){
- if (i>j)
- return;
- if (i==j){
- if (pirates[i] == '0'){
- tree[index].p[1] = 1;
- tree[index].p[0] = 0;
- }
- else{
- tree[index].p[0] = 1;
- tree[index].p[1] = 0;
- }
- tree[index].upd = ' ';
- return;
- }
- int mid = (i+j)/2;
- buildTree(2*index+1,i,mid);
- buildTree(2*index+2,mid+1,j);
- tree[index].p[0] = tree[2*index+1].p[0] + tree[2*index+2].p[0];
- tree[index].p[1] = tree[2*index+1].p[1] + tree[2*index+2].p[1];
- tree[index].upd = ' ';
- }
- void update(int index,int i,int j,int l,int r,char c){
- if (i == l && j == r){
- tree[index].update(c);
- }
- tree[2*index+1].update(tree[index].upd);
- tree[2*index+2].update(tree[index].upd);
- tree[index].S();
- if (i == l && j ==r)
- return;
- if (l>j || r<i || l > r)
- return;
- int mid = (i+j)/2;
- update(2*index+1,i,mid,l,min(r,mid),c);
- update(2*index+2,mid+1,j,max(l,mid+1),r,c);
- tree[index].p[0] = tree[2*index+1].p[0] + tree[2*index+2].p[0];
- tree[index].p[1] = tree[2*index+1].p[1] + tree[2*index+2].p[1];
- }
- int query(int index,int i,int j,int l,int r){
- if (l>j || r<i)
- return 0;
- tree[2*index+1].update(tree[index].upd);
- tree[2*index+2].update(tree[index].upd);
- tree[index].S();
- if (i == l && j == r){
- return tree[index].p[0];
- }
- int mid = (i+j)/2;
- int b1 = query(2*index+1,i,mid,l,min(mid,r));
- int b2 = query(2*index+2,mid+1,j,max(mid+1,l),r);
- return b1+b2;
- }
- int main(void){
- int t;
- scanf("%d",&t);
- for(int z=0; z<t; z++){
- int m,len=0,T,q,querycnt=1;
- char str[64];
- scanf("%d",&m);
- for(int i=0; i<m; i++){
- scanf("%d %s",&T,str);
- for(int j=0; j<T; j++){
- int length = strlen(str);
- for(int k=0; k<length; k++){
- pirates[len] = str[k];
- len++;
- }
- }
- }
- buildTree(0,0,len-1);
- scanf("%d",&q);
- printf("Case %d:\n",z+1);
- for(int i=0; i<q; i++){
- char cmd;
- int l,r;
- scanf(" %c %d %d", &cmd, &l, &r);
- if (cmd == 'S'){
- int ans = query(0,0,len-1,l,r);
- printf("Q%d: %d\n",querycnt++,ans);
- }
- else{
- update(0,0,len-1,l,r,cmd);
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement