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>
- #include <list>
- #define s(a) scanf("%d",&a)
- #define ss(a,b) scanf("%d %d",&a,&b)
- #define p(a) printf("%d\n",a)
- #define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
- #define pi pair<int,int>
- #define vi vector<int>
- #define all(v) v.begin(),v.end()
- #define PB push_back
- #define MP make_pair
- #define sz(a) (int)(a).size()
- #define FOR(i,a,b) for(int (i) = (a); (i) < (b); ++(i))
- #define RFOR(i,a,b) for(int (i) = (a)-1; (i) >= (b); --(i))
- #define CLEAR(a) memset((a),0,sizeof(a))
- #define INF 100000000
- #define PI 2*acos(0.0)
- using namespace std;
- typedef long long ll;
- string convertInt(int number)
- {
- stringstream ss;//create a stringstream
- ss << number;//add number to the stream
- return ss.str();//return a string with the contents of the stream
- }
- int convertString(string s){
- int num;
- stringstream sstr(s); // create a stringstream
- sstr>>num; // push the stream into the num
- return num;
- }
- class Node{
- public:
- char upd;
- // 0 - Buccaneer pirates
- // 1 - Barbary pirates
- int p[2];
- Node(){
- CLEAR(p);
- 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(){
- //cout<<"before"<<upd<<" "<<p[0]<<" "<<p[1]<<endl;
- 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 = ' ';
- //cout<<"after"<<upd<<" "<<p[0]<<" "<<p[1]<<endl;
- }
- };
- vector<Node> tree(2048100);
- char pirates[1024001];
- 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;
- cin>>t;
- FOR(z,0,t){
- //CLEAR(tree);
- //CLEAR(pirates);
- int m,len=0,t,q,querycnt=1;
- char str[64];
- s(m);
- FOR(i,0,m){
- cin>>t>>str;
- FOR(j,0,t){
- int length = strlen(str);
- FOR(k,0,length){
- pirates[len] = str[k];
- len++;
- }
- }
- }
- buildTree(0,0,len-1);
- cin>>q;
- printf("Case %d:\n",z+1);
- FOR(i,0,q){
- char cmd;
- int l,r;
- cin>>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