理清条件+维护一堆东西：0118B

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135685272

http://47.92.197.167:5283/contest/454/problem/2

暴力思路，也就是我们要维护的是。从上一行过来的时候，找到第一个不能继续保持1的位置，在它前面找到第一个可以从0变成1的位置变成1，然后把那个位置后面全部清空。

在这里插入图片描述

我们现在要实现的是什么：

  1. 找到第一个非法位置，设为 ii

  2. 找到 ii 前面第一个可以从0变1的位置，设为 jj

  3. 把 jj 后面的1全部清掉

假设我们能够做。每次只会加入1，所以直接暴力清空3.中的是没问题的。

对于2.，我们如果直接找下一个任意位置，可能现在已经是1了，但这无所谓，我们就继续找。而刚刚那个位置未来肯定会被删掉，所以复杂度也是对的。

对于1.，我们感觉很难处理。此时我们可以考虑按列维护，维护当前选了的每一列什么时候挂掉。

开一堆set来搞。

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
#define mo (int)(1e9 + 7)
#define N 1010
int Pow2(int b) {
	int ans = 1, a = 2; 
	while(b) {
		if(b & 1) ans *= a; 
		a *= a; b >>= 1; 
		ans %= mo; a %= mo; 
	}
	return ans; 
}
void Mod(int &a) { if(a <= -mo || a >= mo) a %= mo; if(a < 0) a += mo; }
struct node {
	int x, l, r; 
	bool operator < (const node &A) const {
		if(x == A.x) {
			if(l == A.l) return r < A.r; 
			return l < A.l; 
		}
		return x < A.x; 
	}
};
multiset<node>S; 
struct Node {
	int x, t; 
	bool operator < (const Node &A) const {
		if(t == A.t) return x < A.x; 
		return t < A.t; 
	}
};
multiset<Node>s2; 
multiset<int>s[N], s1; 
int n, m, i, j, k, T, q, ans, sum, op, mx;

int qtm(int i, int j) {
	auto it = S.lower_bound({i, j, j}); 
//	debug("I find it [%lld [%lld %lld]]\n", (*it).x, (*it).l, (*it).r); 
	if(it != S.end() && (it -> x) == i && (it -> l) == j) return it -> r; 
	else return --it, (it -> r); 
}

void add(int i, int j) {
	assert(s1.find(j) == s1.end()); 
//	debug("Insert %lld\n", j); 
	s1.insert(j); sum += Pow2(j); Mod(sum); 
	int t = qtm(j, i); 
//	debug("qtm[%lld in %lld] is %lld || %lld\n", j, i, t, s2.size()); 
//	for(auto t: s2) debug("== %lld %lld\n", t.x, t.t); 
	assert(s2.find({j, t}) == s2.end()); 
	s2.insert({j, t}); 
}

void del(int j, int et) {
//	debug("Erase %lld\n", j); 
	sum -= Pow2(j); Mod(sum); 
	assert(s1.find(j) != s1.end()); 
	s1.erase(j); 
	assert(s2.find({j, et}) != s2.end()); 
	s2.erase({j, et}); 
}

signed main()
{
//	#ifdef LOCAL
	  freopen("price.in", "r", stdin);
	  freopen("price.out", "w", stdout);
//	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n = read(); m = read(); q = read(); 
	while(q--) {
		op = read(); 
		if(op == 1) {
			i = read(); j = m - read(); 
			if(s[i].find(j) != s[i].end()) s[i].erase(j); 
			else s[i].insert(j); 
			if(S.empty()) S.insert({j, i, i}); 
			else {
				auto it = S.lower_bound({j, i, i}); 
				if(it != S.end() && (it -> l) == i && (it -> x) == j) {
					if((it -> l) == (it -> r)) S.erase(it); 
					else S.insert({j, i + 1, (it -> r)}), S.erase(it); 
				}
				else {
//						debug("At(%lld %lld) (%lld)[%lld %lld]\n", i, j, (*it).x, (*it).l, (*it).r); 
					if(it != S.begin()) --it; 
					if((it -> x) == j && (it -> l) <= i && (it -> r) >= i) {
						if(i != (it -> l)) S.insert({j, (it -> l), i - 1}); 
						if(i != (it -> r)) S.insert({j, i + 1, (it -> r)}); 
						S.erase(it); 
					}
					else {
						int L = i, R = i; 
						if((it -> x) == j && (it -> r) == i - 1) {
							L = (it -> l); auto it1 = it; ++it; 
							S.erase(it1); 
						}
						else if((it -> x) == j && (it -> l) == i + 1) {
							R = (it -> r); auto it1 = it; ++it; 
							S.erase(it1); 
						}
						else ++it; 
						if(it != S.end() && (it -> x) == j && (it -> l) == i + 1) {
							R = (it -> r); S.erase(it); 
						}
						S.insert({j, L, R}); 
					}
				}
			}
//			for(auto t : S) debug("%lld [%lld %lld]\n", t.x, t.l, t.r); 
//			debug("---\n"); 
		}
		else {
//			for(auto t : S) debug("%lld [%lld %lld]\n", t.x, t.l, t.r); 
			s1.clear(); s2.clear(); sum = ans = 0; 
			if(s[1].empty()) { printf("-1\n"); continue; }
			auto it = s[1].begin(); 
			add(1, *it); ans += sum; Mod(ans); 
//			debug("<1> [%lld]%lld\n", *it, sum); 
			for(i = 2; i <= n; ++i) {
				mx = -1; 
				assert(s1.size() == s2.size()); 
				while(!s2.empty() && (*s2.begin()).t < i) {
					auto t = (*s2.begin()); 
					mx = max(mx, t.x); 
//					debug("I make a delete\n"); 
					del(t.x, t.t); 
				}
				auto it = s[i].upper_bound(mx); 
//				debug("<%lld> mx %lld *it %lld | sum %lld || %lld\n", i, mx, *it, sum, (*s2.begin()).t); 
				int flg = 0; 
				if(it == s[i].end()) break; 
				while(s1.find(*it) != s1.end()) {
					mx = (*it);  
					it = s[i].upper_bound(mx); 
					if(it == s[i].end()) { flg = 1; break; }
				}
				if(flg) break; 
				mx = (*it);  
//				debug("lst mx : %lld\n", mx); 
				while(!s1.empty() && (*s1.begin()) < mx) {
					int k = (*s1.begin()); 
					del(k, qtm(k, i)); 
				}
				add(i, mx); 
//				debug("[%lld]>> %lld\n", i, sum); 
				ans += sum; Mod(ans); 
			}
			if(i <= n) { printf("-1\n"); continue; }
			printf("%lld\n", ans); 
		}
	}
	return 0;
}