题解 P3797 【妖梦斩木棒】
Flandre_495 · · 题解
前面所有人都写了线段树题解，我来写个分块的。
跟线段树比起来，这题用分块会慢一点，但代码很好理解，在细节的处理上比线段树容易的多。所以建议学会这种解题思路，分块可以解决很多线段树很难解决的事。
把 n 个点分成 sqrt(n) 块，维护每块的完整木棒数量，是否有左右圆头。
用分块思想可以很直接很简单地修改或查询。
具体讲解在代码中。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define QWQ cout<<"QwQ"<<endl;
#include<vector>
#include<queue>
#include<stack>
#include<map>
using namespace std;
const int qwq=303030;
const int N=101010;
const int inf=0x3f3f3f3f;
//冗长的日常码前操作；
int n,m;
struct K {
int l,r; //左右边界；
bool zuo,you; //是否有左右圆头木棒；
int sum; //块中整个的木棒数；
} k[N];
char a[qwq]; //记录每一块的状态；
char cz[3]; //用字符串读入，就避免读入空行或括号了；
int t;
inline K search(int x,int y) { //访问块中信息；
K res = (K) { x,y,0,0,0 };
char now = 0; //now记录木棍状态；
for(int i=x; i<=y; i++)
{
if( a[i]=='(' )
now = '(';
if( a[i]==')' )
{
if(now== 0 ) res.zuo = 1; //判断向左圆头；
if(now=='(') res.sum++; //完整块；
now = ')';
}
}
if(now=='(')
res.you = 1; //判断向右圆头；
return res; //返回块中信息；
}
inline void change(int x,char z) {
a[x] = z;
for(int i=1; i<=t; i++)
if(x>=k[i].l && x<=k[i].r) //找到x所属块；
{
k[i] = search( k[i].l,k[i].r ); //修改块中信息；
return ;
}
}
inline int query(int x,int y) {
int ans = 0;
bool yuan = 0; //是否有向右的圆头；
for(int i=1; i<=t; i++)
{
if(k[i].l<=x && y<=k[i].r) //整个在块中；
{
K res = search( x,y );
return res.sum;
}
else if(x>=k[i].l && x<=k[i].r) //左端在块中；
{
K res = search( x,k[i].r );
ans += res.sum;
yuan = res.you;
}
else if(x<k[i].l && k[i].r<y) //块在询问区间中；
{
ans += k[i].sum;
if( k[i].zuo && yuan ) ans++; //左右对上；
if( (!k[i].sum) && (!k[i].you) && (!k[i].zuo) ) continue;
//注意这里有一个陷阱：块中全为X（空块）。
//如果你想记录是否有向右圆头,不能用这个空块来修改；
//可以证明：一个块当它既无完整木棒又无向左向右圆头时为空块。
yuan = k[i].you;
}
else if(y>=k[i].l && y<=k[i].r) //右端在块中；
{
K res = search( k[i].l,y);
ans += res.sum;
if( res.zuo && yuan) ans++;
return ans;
}
}
return ans;
}
int main() {
int x,y;
scanf("%d%d",&n,&m);
//开始建造分块；
t = sqrt(n);
for(int i=1; i<=t; i++) {
k[i].l = k[i-1].r + 1;
k[i].r = i * t;
}
if(k[t].r != n) {
t++;
k[t].l = k[t-1].r + 1;
k[t].r = n;
}
a[1] = '('; k[1].you = 1;
a[n] = ')'; k[t].zuo = 1;
//左右一改，建造完成；
while( m-- ) {
scanf("%d",&x);
if(x==1) {
scanf("%d%s",&x,cz);
change( x,cz[0] );
} else {
scanf("%d%d",&x,&y);
printf("%d\n", query(x,y) );
}
}
return 0;
}