欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JZOJ 4273. 【NOIP2015模拟10.28B组】圣章-精灵使的魔法语

程序员文章站 2022-06-03 08:30:42
4273. 【NOIP2015模拟10.28B组】圣章-精灵使的魔法语 (File IO): input:elf.in output:elf.out Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits Goto ProblemS ......

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 }