P2184 贪婪大陆

it2022-05-06  0

/* 该题目地雷种数是累加而不是覆盖, 所以我们对于每次询问实际上是去查询有多少个区间与查询区间有公共部分 我们用总区间数目减去没有覆盖的区间数即可 这个可以通过维护左右端点的和来做到 于是线段树 */ #include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<queue> #define M 100010 #define lson l, mid, now << 1 #define rson mid + 1, r, now << 1 | 1 using namespace std; int n, m, cnt; struct T { int t[M << 2]; int query(int l, int r, int now, int ln, int rn) { if(l > rn || r < ln || ln > rn) return 0; if(l >= ln && r <= rn) return t[now]; int mid = (l + r) >> 1; return query(lson, ln, rn) + query(rson, ln, rn); } void modify(int l, int r, int now, int k) { if(l > k || r < k) return; if(l == r) { t[now]++; return; } int mid = (l + r) >> 1; modify(lson, k), modify(rson, k); t[now] = t[now << 1] + t[now << 1 | 1]; } } tr[2]; int read() { int nm = 0, f = 1; char c = getchar(); for(; !isdigit(c); c = getchar()) if(c == '-') f = -1; for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0'; return nm * f; } int main() { n = read(), m = read(); while(m--) { int q = read(), l = read(), r = read(); if(q == 1) { tr[0].modify(1, n, 1, l); tr[1].modify(1, n, 1, r); cnt++; } else { cout << cnt - tr[1].query(1, n, 1, 1, l - 1) - tr[0].query(1, n, 1, r + 1, n) << "\n"; } } return 0; }

 

转载于:https://www.cnblogs.com/luoyibujue/p/9364664.html

相关资源:垃圾分类数据集及代码

最新回复(0)