Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

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

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

假使操作區間 [a, b] 則紀錄 a-1, b, 將所有不重複的抓出來由小排到大,

則個數不超過 2000 個 a1, a2 ,,, am, 然後統計 (an, an+1] 1 的總個數,

接著模擬求解即可 O(N + Q*Q)

#include <stdio.h>
#include <algorithm>
using namespace std;
char A[1048577];
int encode[1048577], one[2000];
int main() {
    int T, M, N, Q, t, a[1000], b[1000];
    int Case = 0, i, j, k, x, y;
    char str[100], op[1000][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]-'0';
            }
        }
        A[N] = '\0';
        scanf("%d", &Q);
        printf("Case %d:\n", ++Case);
        int QCase = 0, used[2000], ans;
        for(i = 0; i < Q; i++) {
            scanf("%s %d %d", op[i], &a[i], &b[i]);
            a[i]++, b[i]++;
            used[i<<1] = a[i]-1, used[i<<1|1] = b[i];
        }
        sort(used, used+(2*Q));
        encode[used[0]] = 0;
        for(i = 1, j = 0; i < 2*Q; i++) {
            if(used[j] != used[i]) {
                j++;
                used[j] = used[i];
                encode[used[j]] = j;
            }
        }
        for(i = 0; i < j; i++) {
            one[i] = 0;
            for(k = used[i]+1; k <= used[i+1]; k++)
                one[i] += A[k-1];
        }
        for(i = 0; i < Q; i++) {
            x = encode[a[i]-1], y = encode[b[i]]-1;
            if(op[i][0] == 'F') {
                for(j = x; j <= y; j++)
                    one[j] = used[j+1] - used[j];
            } else if(op[i][0] == 'E') {
                for(j = x; j <= y; j++)
                    one[j] = 0;
            } else if(op[i][0] == 'I') {
                for(j = x; j <= y; j++)
                    one[j] = used[j+1] - used[j] - one[j];
            } else {
                for(j = x, ans = 0; j <= y; j++)
                    ans += one[j];
                printf("Q%d: %d\n", ++QCase, ans);
            }
        }
    }
    return 0;
}