校门外的树"/>
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
更多推荐
2019.9.4 校门外的树
发布评论