2019.9.4 校门外的树

校门外的树"/>

2019.9.4 校门外的树

那个校门外的树？你想多了

题目传送门

对于这样定值的区间修改 我们有一种叫做括号序列的方法

我们修改区间时 将其左端点l标记为左括号 右端点右括号

所以我们每次查询时 首先查找右端点左侧有多少个左括号

（即有多少区间起点）

再查找左端点左侧有多少个右括号（已经匹配了多少区间）

二者相减即可

为了维护两个前缀和 我们用两个树状数组

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
int n,m,k,x,y;
int l[1000050],r[1000050];
int lowbit(int x)
{return x&(-x);
}
void addl(int i,int x)
{while(i<=n){l[i]+=x;i+=lowbit(i);}
}
void addr(int i,int x)
{while(i<=n){r[i]+=x;i+=lowbit(i);}
}
int queryl(int i)
{int res=0;while(i>=1){res+=l[i];i-=lowbit(i);}return res;
}
int queryr(int i)
{int res=0;while(i>=1){res+=r[i];i-=lowbit(i);}return res;
}
signed main()
{scanf("%lld%lld",&n,&m);for(int i=1;i<=m;i++){scanf("%lld%lld%lld",&k,&x,&y);if(k==1){addl(x,1);addr(y,1);}if(k==2)printf("%lld\n",queryl(y)-queryr(x-1));}return 0;
}

转载于:.html