11402. Ahoy, Pirates!

In the ancient pirate ages, the Pirate Land was divided into two teams of pirates, namely, the Buccaneer and the Barbary pirates. Each pirate's team was not fixed, sometimes the opponent pirates attacked and he was taken away to the other pirate team. All on a sudden a magician appeared in the Pirate Land, where he was making transition of pirates from their team to other team at his own will. Of course, handy spells were used. The process of changing team was known as mutating.

There were n pirates and all of the pirates have a unique id from 0 to n – 1. The great magician could mutate a bunch of pirates with consecutive id's to another one.

Suppose there were 100 pirates in the pirate land and all of them were Barbary pirates, then the magician could cast a spell to change pirates with id's from 10 to 33 to Buccaneer pirates. Then the whole pirate land would have 24 Buccaneer and 76 Barbary pirates.

The magician was very fast casting the spell. Once, God started to dislike this. God had favor for the Buccaneer pirates and God asked the magician, “Tell me, how many of the pirates of index from 2 to 30 are Buccaneer pirates?” Now the magician was puzzled as he was only efficient in casting spells, not in counting :-)

Being clever enough, the magician captured a clever man from the Earth Land. And unfortunately its you! Now you have to answer the Gods questions.

Input. The first line of input will contain number of test cases t. For each test case:

The first part of the description will be of the pirate land. There could be up to n (1 ≤ n ≤ 1024000) pirates. Each pirate is either assigned to Buccaneer or Barbary Pirate. Buccaneer pirates are described by `1' (ONE) and Barbary pirates are described by `0' (ZERO). You have to build a string of the pirates description. Each case starts with an integer m (m ≤ 100), where m pair lines follow. In each pair of lines (we call it a set), first has an integer t (t ≤ 200) and next one has a nonempty string Pirates (consisting of 0 and 1, 0 for Barbary, 1 for Buccaneer, has maximum length of 50). For each pair concatenate the string Pirates, t times. Concatenate all the resulting m sets of strings to build the pirate description. The final concatenated string describes the pirates from index 0 to end (n – 1 for n pirates).

Now the next part of the input will contain queries. First line of next part has an integer q describing number of queries. Each subsequence q (1 ≤ q ≤ 1000) lines describe each query. Each query has a string F or E or I or S and two integers, a and b denoting indexes. The meaning of the query string are follows:

F a b, means, mutate the pirates from index a to b to Buccaneer Pirates.

E a b, means, mutate the pirates from index a to b to Barbary Pirates.

I a b, means, mutate the pirates from index a to b to inverse pirates.

S a b, means “God's query" God is asking a question: “Tell me, how many Buccaneer pirates are

there from index a to b?"

(a ≤ b, 0 ≤ a < n, 0 ≤ b < n, index range are inclusive)

Output. For each test print the case number as the sample output suggests. Then for each of God's query, output the query number, colon (:) and a space and the answer to the query as the sample suggest.

Sample Input

1000

F 0 17

I 0 5

S 1 10

E 4 9

S 2 10

I 0 2

S 0 8

Sample Output

Case 1:

Q1: 5

Q2: 1

Case 2:

Q1: 0

РЕШЕНИЕ

дерево отрезков

Анализ алгоритма

На дереве отрезков следует промоделировать четыре операции.

Реализация алгоритма

#include <cstdio>

#include <cstring>

#include <vector>

#define MAX 1024010

#define NORMAL 0

#define SET 1

#define CLEAR 2

#define FLIP 3

using namespace std;

int i, j, k, t, n, m, tests, cs, q, q1;

int l, r;

struct node

{

int summa, type;

};

vector<node> SegTree;

char ch, s[100];

int a[MAX];

void build(int *a, int Vertex, int Left, int Right)

{

SegTree[Vertex].type = NORMAL;

if (Left == Right)

SegTree[Vertex].summa = a[Left];

else

{

int Middle = (Left + Right) / 2;

build (a,2*Vertex, Left, Middle);

build (a,2*Vertex+1, Middle+1, Right);

SegTree[Vertex].summa = SegTree[2*Vertex].summa + SegTree[2*Vertex+1].summa;

}

int ApplyFlip(int type)

{

if (type == SET) return CLEAR;

if (type == CLEAR) return SET;

if (type == FLIP) return NORMAL;

return FLIP; // type = NORMAL

}

void Push(int Vertex, int LeftPos, int Middle, int RightPos)

{

if (SegTree[Vertex].type == SET)

{

SegTree[2*Vertex].type = SegTree[2*Vertex+1].type = SegTree[Vertex].type;

SegTree[2*Vertex].summa = Middle - LeftPos + 1;

SegTree[2*Vertex+1].summa = RightPos - Middle;

SegTree[Vertex].type = NORMAL;

} else

if (SegTree[Vertex].type == CLEAR)

{

SegTree[2*Vertex].type = SegTree[2*Vertex+1].type = SegTree[Vertex].type;

SegTree[2*Vertex].summa = SegTree[2*Vertex+1].summa = 0;

SegTree[Vertex].type = NORMAL;

} else

if (SegTree[Vertex].type == FLIP)

{

SegTree[2*Vertex].type = ApplyFlip(SegTree[2*Vertex].type);

SegTree[2*Vertex+1].type = ApplyFlip(SegTree[2*Vertex+1].type);

SegTree[2*Vertex].summa = Middle - LeftPos + 1 - SegTree[2*Vertex].summa;

SegTree[2*Vertex+1].summa = RightPos - Middle - SegTree[2*Vertex+1].summa;

SegTree[Vertex].type = NORMAL;

}

void Set(int Vertex, int LeftPos, int RightPos, int Left, int Right)

{

if (Left > Right) return;

if ((LeftPos == Left) && (RightPos == Right))

{

SegTree[Vertex].type = SET;

SegTree[Vertex].summa = Right - Left + 1;

return;

}

int Middle = (LeftPos + RightPos) / 2;

Push(Vertex,LeftPos,Middle,RightPos);

Set(2*Vertex, LeftPos, Middle, Left, min(Middle,Right));

Set(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1), Right);

SegTree[Vertex].summa = SegTree[2*Vertex].summa + SegTree[2*Vertex+1].summa;

}

void Clear(int Vertex, int LeftPos, int RightPos, int Left, int Right)

{

if (Left > Right) return;

if ((LeftPos == Left) && (RightPos == Right))

{

SegTree[Vertex].type = CLEAR;

SegTree[Vertex].summa = 0;

return;

}

int Middle = (LeftPos + RightPos) / 2;

Push(Vertex,LeftPos,Middle,RightPos);

Clear(2*Vertex, LeftPos, Middle, Left, min(Middle,Right));

Clear(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1), Right);

SegTree[Vertex].summa = SegTree[2*Vertex].summa + SegTree[2*Vertex+1].summa;

}

void Flip(int Vertex, int LeftPos, int RightPos, int Left, int Right)

{

if (Left > Right) return;

if ((LeftPos == Left) && (RightPos == Right))

{

SegTree[Vertex].type = ApplyFlip(SegTree[Vertex].type);

SegTree[Vertex].summa = Right - Left + 1 - SegTree[Vertex].summa;

return;

}

int Middle = (LeftPos + RightPos) / 2;

Push(Vertex,LeftPos,Middle,RightPos);

Flip(2*Vertex, LeftPos, Middle, Left, min(Middle,Right));

Flip(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1), Right);

SegTree[Vertex].summa = SegTree[2*Vertex].summa + SegTree[2*Vertex+1].summa;

}

int Summa(int Vertex, int LeftPos, int RightPos, int Left, int Right)

{

if (Left > Right) return 0;

if ((LeftPos == Left) && (RightPos == Right))

return SegTree[Vertex].summa;

int Middle = (LeftPos + RightPos) / 2;

Push(Vertex,LeftPos,Middle,RightPos);

return Summa(2*Vertex, LeftPos, Middle, Left, min(Middle,Right)) +

Summa(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1), Right);

}

int main(void)

{

scanf("%d",&tests);

for(cs = 1; cs <= tests; cs++)

{

scanf("%d",&m); n = 0;

for(i = 0; i < m; i++)

{

scanf("%d\n",&t);

gets(s);

for(k = 0; k < t; k++)

for(j = 0; j < strlen(s); j++)

a[n++] = s[j] - '0';

}

SegTree.resize(4*n);

build(a,1,0,n-1);

printf("Case %d:\n",cs);

scanf("%d\n",&q); q1 = 1;

for(j = 0; j < q; j++)

{

scanf("%c %d %d\n",&ch,&l,&r);

if (ch == 'F')

Set(1,0,n-1,l,r);

else

if (ch == 'E')

Clear(1,0,n-1,l,r);

else

if (ch == 'I')

Flip(1,0,n-1,l,r);

else // ch == 'S'

printf("Q%d: %d\n",q1++,Summa(1,0,n-1,l,r));

}

return 0;

}