JZOJ 4273. 【NOIP2015模擬10.28B組】聖章-精靈使的魔法語

4273. 【NOIP2015模擬10.28B組】聖章-精靈使的魔法語 (File IO): input:elf.in output:elf.out Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits Goto ProblemS ...

4273. 【NOIP2015模擬10.28B組】聖章-精靈使的魔法語
(File IO): input:elf.in output:elf.out

Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits Goto ProblemSet

Description

【背景介紹】
“魔法？？？算了吧，這種東西我肯定學不了的啦！”明明是個劍士，卻被眼前這位洋洋自得的精靈使——弗洛莉拖出去學魔法，真是個沒事找茬的家伙……
“沒事啦。作為一名冒險者會發生很多情況，中毒啦，受傷啦，被咒語束縛之類的，沒有魔法就很難辦的呀！”她到是好像一副什麼都懂的樣子，真是令人火大。
“都說我是個人類了，魔法這種東西學起來很困難的吧！”我只好找個看似靠譜的藉口。
然而，她那不屈不撓的聲音又響了起來：“人類雖然與自然的共鳴，也就是魔法的連接較少，但如果認真訓練的話還是可以做到的呢！總之，試試看吧！念念咒語之類的！”弗洛莉把魔法書一把拍在了我面前。
我沒興趣地瞟了一眼，“哼。這種東西我不看也會，倫福薩——密西卡！”才剛剛念完不知道從哪裡偷學來的魔法咒語。隨即，便聽到弗洛莉的一聲尖叫，使得整個酒店的人的視線都往這邊看來。喂喂喂，別往我這邊看啊，我有視線恐懼症啊！！！！況且，我只是把她正在吃的麵包的樣子變成蟲子而已，誰會料到這種情況啊啊啊！！
“真是的，弗洛莉才是老拖我的後腿呢！”我沒好氣地笑道……
“里修！你……”她從牙縫裡擠出了一個字。我頓感不妙，見到了那張比魔鬼還可怕的扭曲的面孔。“真是個魔法的天才哪！”她一掃之前不愉快的表情，想我露出大拇指，好像是在誇獎我的樣子。
咦？她竟然沒有打我，那真是我福大命大。我這樣想著，便一屁股坐在了凳子上，鬆了口氣……
【題目描述】
“倫福薩”【即" ( "】和“密西卡”【即" ) "】是兩種不同的精靈咒語，已知一個成功的咒語符合如下的規定：
每一個密西卡之前都可以對應匹配到一個倫福薩，即為一個合法的精靈魔法咒語。
方便的是，我們將“倫福薩”視為" ( "，“密西卡”視為" ) "，合法的精靈魔法咒語即為一個合法的括弧序列。
如：" ( ( ( ) ) ) "" ( ( ) ( ) ) "" ( ) ( ) ( ) "均為合法的魔法咒語，" ) ( "" ( ) ) ( "" ( ( "均為不合法的魔法咒語。
現在弗洛莉給我一個長長的“倫福薩”【即" ( "】和“密西卡”【即" ) "】的片段，每次給我一個l和r，讓我判斷需要在這個片段前最少添多少個“倫福薩”【即" ( "】，以及最少添多少個“密西卡”【即" ) "】可以成為一個合法的魔法咒語，更令人不爽的是，弗洛莉有的時候還會把一個“倫福薩”【即" ( "】變成“密西卡”【即" ) "】，或把一個“密西卡”【即" ) "】變為“倫福薩”【即" ( "】。

Input

第一行兩個正整數n,m，表示我現在含有的咒語元素（“倫福薩”【即" ( "】和“密西卡”【即" ) "】）的個數以及弗洛莉給我的任務個數，
第二行包含n個字元（“倫福薩”【即" ( "】或“密西卡”【即" ) "】）表示一開始弗洛莉給我的咒語片段。
以下m行包括兩種任務：
Change x，表示弗洛莉將位置為x上的咒語片段進行一次變換（原來是“倫福薩”【即" ( "】變為“密西卡”【即" ) "】，原來是“密西卡”【即" ) "】變為“倫福薩”【即" ( "】）。
Query l r，詢問從l到r的區間的片段，在這個片段前最少添上多少個倫福薩”【即" ( "】，在這個片段後最少添上多少個“密西卡”【即" ) "】可以成為合法的魔法序列。

Output

每個詢問對應一行答案，每行包括兩個整數，表示在這個片段前最少添上多少個倫福薩”【即" ( "】，在這個片段後最少添上多少個“密西卡”【即" ) "】可以成為合法的魔法序列。

Sample Input

6 4
(()()(
Query 1 3
Query 3 6
Change 6
Query 1 6

Sample Output

0 1
1 1
0 0
【樣例解釋】
1.片段為“ ( ( ) ”最右邊填1個 ) 即可。
2.片段為“ ) ( ) ( ”最左邊添1個 ( 最右邊添1個 ) 即可。
3.片段為“ ( ( ) ( ) ) ”已經是合法片段。不需添加。

Data Constraint

對於20%的數據，1 ≤ n,m ≤ 100
對於40%的數據，1 ≤ n,m ≤ 3000
另外含有30%的數據，數據中不包含修改操作。
對於100%的數據，1 ≤ n,m ≤ 150,000

做法：線段樹，線段樹維護兩個值，一個是當前區間內有多少個多餘的“（”，另一個值是區間內需要多少個“（”，即有多少個“）” 沒有被匹配，更新一個區間時：（以下右子樹用 right 表示，左子樹用 left 表示）：多餘的“（”=right 多餘的“（”+max（left 多餘的“（”- right 需要的“（” ，0）（取 max 是因為會出現左子樹多餘的“（”還是不夠右子樹用的情況）需要的“（”=left 需要的“（”+max（right 需要的“（”- left 多餘的“（” ，0）（取 max 是因為會出現右子樹需要的全部的“（” 左子樹都填上了的情況）。 代碼如下：

  1 #include <cstring>
  2 #include <cstdio>
  3 #include <iostream>
  4 #include <string>
  5 #include <algorithm>
  6 #define N 1200007
  7 using namespace std;
  8 struct tree
  9 {
 10     int need, more, l, r;
 11 }f[N];
 12 int n, m, L, R, x, y;
 13 char ch[N / 2];
 14 string c;
 15 
 16 inline int read()
 17 {
 18     int s = 0;
 19     char g = getchar();
 20     while (g < '0' || g > '9')    g = getchar();
 21     while (g >= '0' && g <= '9')    s = s * 10 + g - '0', g = getchar();
 22     return s;
 23 }
 24 
 25 inline string read2()
 26 {
 27     string gg = "";
 28     char g = getchar();
 29     while (g < 'A' || g > 'z')    g = getchar();
 30     while (g >= 'A' && g <= 'z')    gg += g, g = getchar();
 31     return gg;    
 32 }
 33 
 34 inline void put(int x)
 35 {
 36     if (x < 0)
 37        x = ~x + 1, putchar('-');    
 38     if (x > 9) 
 39        put(x / 10);putchar(x % 10 + '0');
 40 }
 41 
 42 inline void build(int p)
 43 {
 44     if (f[p].l == f[p].r)
 45     {
 46         if (ch[f[p].l] == '(')    f[p].more = 1;
 47         else f[p].need = 1;
 48         return;
 49     }
 50     int mid = (f[p].l + f[p].r) / 2;
 51     f[p * 2].l = f[p].l;    f[p * 2].r = mid;
 52     f[p * 2 + 1].l = mid + 1;    f[p * 2 + 1].r = f[p].r; 
 53     build(p * 2);
 54     build(p * 2 + 1);
 55     f[p].more = f[p * 2 + 1].more + max(f[p * 2].more - f[p * 2 + 1].need, 0);
 56     f[p].need = f[p * 2].need + max(f[p * 2 + 1].need - f[p * 2].more, 0);
 57     return;
 58 }
 59 
 60 inline void change(int p, int t)
 61 {
 62     if (f[p].l == t && f[p].r == t)
 63     {
 64         f[p].more = 1 - f[p].more;
 65         f[p].need = 1 - f[p].need;
 66         return;
 67     }
 68     if (f[p].l == f[p].r)    return;
 69     int mid = (f[p].l + f[p].r) / 2;
 70     if (t <= mid)    change(p * 2, t);
 71     else change(p * 2 + 1, t);
 72     f[p].more = f[p * 2 + 1].more + max(f[p * 2].more - f[p * 2 + 1].need, 0);
 73     f[p].need = f[p * 2].need + max(f[p * 2 + 1].need - f[p * 2].more, 0);
 74     return;
 75 }
 76 
 77 inline void find(int p, int a, int b)
 78 {
 79     if (f[p].l == a && f[p].r == b)
 80     {
 81         L = f[p].need;
 82         R = f[p].more;
 83         return;
 84     }
 85     if (f[p].l == f[p].r)    return;
 86     int mid = (f[p].l + f[p].r) / 2;
 87     if (b <= mid)
 88     {
 89         find(p * 2, a, b);
 90         return;
 91     }    
 92     if (a > mid)
 93     {
 94         find(p * 2 + 1, a, b);
 95         return;
 96     }    
 97     find(p * 2, a, mid);
 98     int LL = L, RR = R;
 99     find(p * 2 + 1, mid + 1, b);
100     int LLL = L, RRR = R;
101     L = LL + max(LLL - RR, 0);
102     R = RRR + max(RR - LLL, 0);
103     return;    
104 }
105 
106 int main()
107 {
108 //    freopen("elf.in", "r", stdin);
109 //    freopen("elf.out", "w", stdout);
110     n = read(), m = read();
111     cin >> ch + 1;
112     f[1].l = 1;        f[1].r = n;
113     build(1);
114     while (m--)
115     {
116         c = read2();
117         if (c == "Query")
118         {
119             L = 0, R = 0;
120             x = read(), y = read();
121             find(1, x, y);
122             put(L);
123             printf(" ");
124             put(R);
125             printf("\n");
126         }
127         else
128         {
129             x = read();
130             change(1, x);
131         }
132     }
133 }