CF368 D - Persistent Bookcase

re了20多发还是我在测试数据上操作最后了10多发才发现的

其实只需要多加一句就好了

真的愚蠢啊，要不都能进前100了

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 100005;

const int INF = 0x3f3f3f3f;

int sh[1005][1005];

int flag[1005];

int sum[1005];

int all;

int vis[MAXN];

vector<int> mp[MAXN];

int n,m,q;

struct Node{

	int ty; int x,y; int ans;

}as[MAXN];

int cc = 0;

const int Ed = 26;

void dfs(int po,int fa) {

	int x1,x2; int y1,y2,y3,y4; // sh[x1][x2], all, sum[x1], flag[x1]

	for(int i = 0; i < (int)mp[po].size(); ++i) {

		int tt = mp[po][i];

		int t1 = as[tt].ty; int t2 = as[tt].x; int t3 = as[tt].y;

		if(t1 == 4) t2 = 0; // 这地方不写会越界 谨记啊

		x1 = t2; x2 = t3; y1 = sh[x1][x2]; y2 = all; y3 = sum[x1]; y4 = flag[x1];

		if(t1 == 1) {

			if( (flag[t2] ^ sh[t2][t3]) == 0) {

				all ++; sh[t2][t3] ^= 1; sum[t2] ++;

			}

		}else if(t1 == 2) {

			if( (flag[t2] ^ sh[t2][t3]) == 1){

				all--; sh[t2][t3] ^= 1; sum[t2] --;

			}

		}else if(t1 == 3) {

			flag[t2] ^= 1;

			all += m-sum[t2]*2;

		   	sum[t2] = m-sum[t2];

		}

		as[tt].ans = all;

		dfs(tt,po);

		sh[x1][x2] = y1; all = y2; sum[x1] = y3; flag[x1] = y4;

	}

}

int main(){

	while(~scanf("%d %d %d",&n,&m,&q)){

		memset(flag,0,sizeof(flag));

		memset(sh,0,sizeof(sh));

		memset(sum,0,sizeof(sum));

		all = 0;

		cc = 0;

		for(int i = 0; i <= q; ++i) mp[i].clear();

		for(int i = 1; i <= q; ++i) {

			as[i].y = 0;

			scanf("%d",&as[i].ty);

			if(as[i].ty < 3) scanf("%d %d",&as[i].x,&as[i].y);

			else scanf("%d",&as[i].x);

			if(as[i].ty == 4) mp[as[i].x].push_back(i);

			else mp[i-1].push_back(i);

		}

		dfs(0,-1);

		for(int i = 1; i <= q; ++i) printf("%d\n",as[i].ans);

	}

	return 0;

}

巴特西

CF368 D - Persistent Bookcase

最新文章

热门文章