Problem H
Ahoy, Pirates!
Input: Standard
Input
Output: Standard
Output
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 J
Being clever enough, the magician captured a clever man from
the Earth Land.
And unfortunately it’s you! Now you have to answer the God’s 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 Output
for Sample Input
|
2
2
5
10
2
1000
5
F 0 17
I 0 5
S 1 10
E 4 9
S 2 10
3
3
1
4
0
2
0
2
I 0 2
S 0 8
|
Case 1:
Q1: 5
Q2: 1
Case 2:
Q1: 0
|
Explanation:
Case1:
The pirate land is as follows (N = 18)
101010101010001000
Before God’s first query it was as follows
000000111111111111
Case 2:
The pirate land is as follows (N=9)
111000000
題目意思:
將區間的值全部變成 1, 或者是全部變成 0, 或者是 0 1 對調
求區間總和
#include <stdio.h>
#include <string.h>
char A[1048576];
struct st{
int v, l, r, op;
} tree[2097153];
void build(int k, int l, int r) {
tree[k].l = l, tree[k].r = r;
tree[k].v = 0;
if(l == r) {
tree[k].v = A[l]-'0';
tree[k].op = 0;
}
if(l < r) {
int m = (l+r)>>1;
build(k<<1, l, m);
build(k<<1|1, m+1, r);
tree[k].op = 0;
tree[k].v = tree[k<<1].v + tree[k<<1|1].v;
}
}
void single(int k) {
if(tree[k].op) {
if(tree[k].op == 1)
tree[k].v = tree[k].r - tree[k].l + 1;
else if(tree[k].op == 2)
tree[k].v = 0;
else
tree[k].v = tree[k].r - tree[k].l + 1 - tree[k].v;
if(tree[k].l < tree[k].r) {
if(tree[k].op == 3) {
tree[k<<1].op = 3 - tree[k<<1].op;
tree[k<<1|1].op = 3 - tree[k<<1|1].op;
} else {
tree[k<<1].op = tree[k].op;
tree[k<<1|1].op = tree[k].op;
}
}
tree[k].op = 0;
}
}
void modify(int k, int l, int r, int op) {
if(l == tree[k].l && r == tree[k].r) {
if(op == 3)
tree[k].op = 3-tree[k].op;
else
tree[k].op = op;
}
single(k);
if(l == tree[k].l && r == tree[k].r)
return;
int m = (tree[k].l+tree[k].r)>>1;
if(r <= m)
modify(k<<1, l, r, op);
else if(l > m)
modify(k<<1|1, l, r, op);
else {
modify(k<<1, l, m, op);
modify(k<<1|1, m+1, r, op);
}
single(k<<1), single(k<<1|1);
tree[k].v = tree[k<<1].v + tree[k<<1|1].v;
}
int count(int k, int l, int r) {
single(k);
if(l == tree[k].l && r == tree[k].r)
return tree[k].v;
int m = (tree[k].l+tree[k].r)>>1;
if(r <= m)
return count(k<<1, l, r);
else if(l > m)
return count(k<<1|1, l, r);
else {
return count(k<<1, l, m)+count(k<<1|1, m+1, r);
}
single(k<<1), single(k<<1|1);
tree[k].v = tree[k<<1].v + tree[k<<1|1].v;
}
int main() {
int T, M, N, Q, t, i, a, b;
int Case = 0;
char str[100], op[3];
scanf("%d", &T);
while(T--) {
scanf("%d", &M);
N = 0;
while(M--) {
scanf("%d %s", &t, str);
while(t--) {
for(i = 0; str[i]; i++, N++)
A[N] = str[i];
}
}
A[N] = '\0';
build(1, 0, N-1);
scanf("%d", &Q);
printf("Case %d:\n", ++Case);
int QCase = 0;
while(Q--) {
scanf("%s %d %d", op, &a, &b);
if(op[0] == 'F') {//1
modify(1, a, b, 1);
} else if(op[0] == 'E') {//0
modify(1, a, b, 2);
} else if(op[0] == 'I') {//XOR
modify(1, a, b, 3);
} else {
printf("Q%d: %d\n", ++QCase, count(1, a, b));
}
}
}
return 0;
}
