两个管道相交是啥情况？
有环展链 我们把环展成链过后 发现只会出现如下图两种情况
然后我们维护二维BIT1：表示左端点小于等于x 右端点小于等于y的个数
BIT2：左端点大于等于x 右端点小于等于y
BIT3：左端点大于等于x 右端点大于等于y
查询就很简单了
对于操作1相当于一个更新
#include<bits/stdc++.h> #define N 1005 #define M 500005 using namespace std; int n,m,tree1[N][N],tree2[N][N],tree3[N][N]; inline int read(){ int ans=0; char ch=getchar(); while(!isdigit(ch))ch=getchar(); while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar(); return ans; } inline int lowbit(int x) { return x&(-x); } inline int query1(int x,int y) //左端点小于等于x 右端点小于等于y { int ans=0; for(int i=x;i;i-=lowbit(i)) for(int j=y;j;j-=lowbit(j)) ans+=tree1[i][j]; return ans; } inline int query2(int x,int y) //左端点大于等于x 右端点小于等于y { int ans=0; for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j;j-=lowbit(j)) ans+=tree2[i][j]; return ans; } inline int query3(int x,int y) //左端点大于x 右端点大于y { int ans=0; for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=n;j+=lowbit(j)) ans+=tree3[i][j]; return ans; } inline void update1(int x,int y,int v) { for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=n;j+=lowbit(j)) tree1[i][j]+=v; } inline void update2(int x,int y,int v) { for(int i=x;i;i-=lowbit(i)) for(int j=y;j<=n;j+=lowbit(j)) tree2[i][j]+=v; } inline void update3(int x,int y,int v) { for(int i=x;i;i-=lowbit(i)) for(int j=y;j;j-=lowbit(j)) tree3[i][j]+=v; } struct S { int x,y; }guan[M]; int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int opt; opt=read(); if(opt==0) { int x,y; x=read(); y=read(); if(x>y) swap(x,y); int ansl=query1(x,y)-query2(1,x); int ansr=query3(x,y)-query2(y,n); printf("%d\n",ansl+ansr); update1(x,y,1); update2(x,y,1); update3(x,y,1); guan[i].x=x; guan[i].y=y; } if(opt==1) { int pos; pos=read(); int x=guan[pos].x; int y=guan[pos].y; update1(x,y,-1); update2(x,y,-1); update3(x,y,-1); } } }转载于:https://www.cnblogs.com/Patrickpwq/articles/9837552.html
