【NOIP 校内模拟】行星通道计划（二维树状数组）

树状数组）"/>

【NOIP 校内模拟】行星通道计划（二维树状数组）

两个管道相交是啥情况？

有环展链 我们把环展成链过后 发现只会出现如下图两种情况

然后我们维护二维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);}}
}

转载于:.html