【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
");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
",ans);
            add(x,y,1);
        }
        else
        {
            read(a[i].k);
            add(a[a[i].k].x,a[a[i].k].y,-1);
        }
    }
}