[2018.10.23 T2] 行星通道计划

暂无链接

行星通道计划

【题目描述】

在战争胜利后，火星文明已经高度发达。为了更快捷的在行星内转移物资，人类开始了浩浩荡荡的行星通道计划 。

行星通道计划要完成的事情是在火星赤道上选择$n$n个站点(每个站点编号为$1\sim n$1∼n，$n$n个站点按编号依次顺时针排列)。用高强度材料制成笔直的管道穿越赤道截面连接两个站点。这样就可以利用火星自身引力完成物资在赤道上两处地表的快速转移。在这里，由于火星很大，一条管道可以近似为一根直线，而赤道截面可以看做一个圆。

但是在赤道面内修建通道有一个弊端，新修建的通道会和之前修建的通道相交，这样需要花费$1$1的代价衔接两个相交的通道。

在行星通道计划开展的这段时间内，你被任命管理行星通道系统。

具体的来说，你需要快速的按照上级的命令组织进行如下操作：

1、在$n$n个站点中将指定的两个没有连接的站点连接起来，并查询此次修建需要花费的代价。

2、拆除一条已有的管道。(可以在下一次$1$1操作中重新修建)

p.s.保证每次需要连接的两个站点连接时没有其他通道经过这两个站点 。

保证删除的通道当前存在。

【输入】

第一行两个正整数$n,m$n,m分别表示站点数和操作数

接下来$m$m行表示操作：

$op=0$op=0时，输入$x,y(1≤x,y≤n)$x,y(1≤x,y≤n)，表示在编号为$x,y$x,y的站点之间修建管道，并查询花费的代价。

$op=1$op=1时，输入$x$x，表示删除第x次操作修筑的管道。($x$x次操作包含所有$1,2$1,2的操作)

【输出】

对于每一个$1$1操作输出一行，表示本次修筑的代价。

【输入样例】

10 7
0 1 7
0 9 2
0 10 5
1 3
0 3 6
0 4 8
0 5 10

【输出样例】

0
1
2
0
2
4

【提示】

【样例解释】

对于样例，通道系统每一时刻的状态如下：

【数据范围】

题解

把一条$x\to y$x→y的通道看做平面上的点$(x,y)$(x,y)，就能发现每次加入一条边的代价实际上是一个（或两个）矩形内的点数，那么我们就上二维树状数组吧。

出题人还有个很神的题解：

代码

因为出题人的做法如上，导致时限变成了$500ms$500ms，所以我们要把二维树状数组开成二维数组来访问连续内存，封装结构体会$\mathcal{TLE}$TLE。

#include<bits/stdc++.h>
#define lb(x) (x&-x)
using namespace std;
const int N=1005;
struct Q{int op,x,y;}e[500005];
int n,m,r,ans,S[N][N];
char c;
int read()
{
    for(r=0;!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())r=(r<<1)+(r<<3)+c-'0';
    return r;
}
int que(int x,int y){int r=0;for(int i=x;i;i-=lb(i))for(int j=y;j;j-=lb(j))r+=S[i][j];return r;}
void add(int x,int y,int v){for(int i=x;i<=n;i+=lb(i))for(int j=y;j<=n;j+=lb(j))S[i][j]+=v;}
void in(){n=read(); m=read();}
void ac()
{
	for(int i=1,l,r,fl;i<=m;i++)
	{
		e[i].op=read();
		if(e[i].op==0)
		{
			e[i].x=read();e[i].y=read();
			if(e[i].x>e[i].y) swap(e[i].x,e[i].y);
			l=e[i].x,r=e[i].y;
			printf("%d\n",que(l-1,r-1)-que(l-1,l)+que(r-1,n)-que(r-1,r)-que(l,n)+que(l,r));
			add(l,r,1);
		}	
		else{fl=read();add(e[fl].x,e[fl].y,-1);}
	}
}
int main(){in(),ac();}