行星通道计划"/>
【NOIP模拟】行星通道计划
题面
时限500ms
分析
考完才发现,很裸的二维树状数组也能过
可以画图发现,能满足两条线相交,只有两种情况 :
1.大的比大的大,小的在中间(9比7大,2在1和7中间)
2.小的比小的小,大的在中间(或者说1比2小,7在2和9中间)
还有各种修改操作,第一个想到的就是树状数组,线段树之类的。
而二维树状数组维护的就是动态二维前缀和,根据我们推出来的结论,超适合做此题。
设x<y,把两端分别为x和y的一条线段加入二维树状数组的(x,y)位置
看下面此图,红色和蓝色矩形中的权值,就是我们要求的。根据上面两句话推出来的。
代码
- #include<bits/stdc++.h>
- using namespace std;
- #define N 1010
- #define M 500050
- int n,m;
- int t[N][N];
- struct email
- {
- int x,y,c,k;
- }a[M];
- template<class T>
- void read(T &x)
- {
- x=0;
- static char c=getchar();
- while(c<'0'||c>'9') c=getchar();
- while(c>='0'&&c<='9')
- x=x*10+c-'0',c=getchar();
- }
- inline int lowbit(int x){return x&(-x);}
- inline void add(int x,int y,int v)
- {
- for(int i=x;i<=n;i+=lowbit(i))
- for(int j=y;j<=n;j+=lowbit(j))
- t[i][j]+=v;
- }
- inline int query(int x,int y)
- {
- if(x<=0||y<=0) return 0;
- int ret=0;
- for(int i=x;i;i-=lowbit(i))
- for(int j=y;j;j-=lowbit(j))
- ret+=t[i][j];
- return ret;
- }
- int main()
- {
- read(n);read(m);
- for(int i=1;i<=m;i++)
- {
- read(a[i].c);
- if(a[i].c==0)
- {
- read(a[i].x),read(a[i].y);
- if(a[i].x>a[i].y)swap(a[i].x,a[i].y);
- int x=a[i].x,y=a[i].y;
- if(y-x<2){printf("0\n");continue;}
- int ans=query(x-1,y-1)-query(x-1,x)+query(y-1,n)-query(x,n)-query(y-1,y)+query(x,y);
- printf("%d\n",ans);
- add(x,y,1);
- }
- else
- {
- read(a[i].k);
- add(a[a[i].k].x,a[a[i].k].y,-1);
- }
- }
- }
转载于:.html
更多推荐
【NOIP模拟】行星通道计划
发布评论