本文共 3737 字，大约阅读时间需要 12 分钟。
提供两种思路
#include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int N = 6e5+5;#define MS(x,y) memset(x,y,sizeof(x))#define MP(x, y) make_pair(x, y)#define lson l, m, rt<<1#define rson m+1, r, rt<<1|1int main() { int n, q; while(~scanf("%d %d", &n, &q)) { map mp; mp[-1] = -1; mp[1] = n; mp[n+1] = INF; int ans = n; while(q --) { int l, r, k; scanf("%d %d %d", &l, &r, &k); int tt = r; if(k == 2 && r != n) tt = r+1; auto it = mp.upper_bound(l); auto it2 = mp.upper_bound(tt); it --; it2 --; int head1 = it -> first; int len1 = it -> second; int head2 = it2 -> first; int len2 = it2 -> second; while(1){ int flag = 0; if(it == it2) flag = 1; ans -= it->second; auto tmp = it; // if(it->first == n+1) while(1); it ++; // printf("erase: %d\n", tmp->first); mp.erase(tmp); if(flag) break; } //for(auto i = mp.begin(); i != mp.end(); ++i) printf("%d:%d ", i->first, i->second); printf("\n"); // printf("%d %d %d %d %d %d\n", head1, len1, head2, len2, l, r); if(k == 1) { if(head1 + len1 - 1 >= l && l!=head1) { mp[head1] = l - head1; ans += l - head1; } else if(l != head1){ mp[head1] = len1; ans += len1; } if(head2 + len2 - 1 > r) { mp[r+1] = head2 + len2 - 1 - r; ans += head2 + len2 - 1 - r; } } else { int L = l; int R = max(r, head2 + len2 -1); if(head1 + len1 < l) { mp[head1] = len1; ans += len1; }else L = head1; mp[L] = R-L+1; ans += R-L+1; } // for(auto i = mp.begin(); i != mp.end(); ++i) printf("%d:%d ", i->first, i->second); printf("\n"); printf("%d\n", ans); } } return 0;}
#include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int N = 6e5+5;#define MS(x,y) memset(x,y,sizeof(x))#define MP(x, y) make_pair(x, y)#define lson l, m, rt<<1#define rson m+1, r, rt<<1|1int Q[N][3];int has[N * 2]; int cnt;int sum[N << 2];int lazy[N << 2];void build(int l, int r, int rt) { lazy[rt] = 0; sum[rt] = has[r] - has[l-1]; if(l == r) { return; } int m = (l + r) >> 1; build(lson); build(rson);}void update(int ty, int L, int R, int l, int r, int rt) { //printf("%d %d\n", l, r); if(L <= has[l-1]+1 && has[r] <= R) { lazy[rt] = ty == 1? -1 : 1; sum[rt] = ty == 1? 0 : has[r] - has[l-1]; return; } int m = (l + r) >> 1; if(lazy[rt] == 1) { lazy[rt<<1] = 1; sum[rt<<1] = has[m] - has[l-1]; lazy[rt<<1|1] = 1; sum[rt<<1|1] = has[r] - has[m]; lazy[rt] = 0; } else if(lazy[rt] == -1){ lazy[rt<<1] = -1; sum[rt<<1] = 0; lazy[rt<<1|1] = -1; sum[rt<<1|1] = 0; lazy[rt] = 0; } if(L <= has[m-1]+1) update(ty, L, R, lson); if(R > has[m]) update(ty, L, R, rson); sum[rt] = sum[rt<<1] + sum[rt<<1|1];}void debug(int l, int r, int rt) { printf("%d %d %d\n", l, r, sum[rt]); if(l == r) return; int m = (l + r) >> 1; debug(lson); debug(rson);}int main() { int n; while(~scanf("%d", &n)) { cnt = 0; int q; scanf("%d", &q); for(int i = 0; i < q; ++i) { scanf("%d %d %d", &Q[i][0], &Q[i][1], &Q[i][2]); has[cnt ++] = Q[i][0] - 1; has[cnt ++] = Q[i][1]; } has[cnt ++] = 0; has[cnt ++] = n; sort(has, has+cnt); cnt = unique(has, has + cnt) - has;// for(int i = 0; i < cnt; ++i) printf("%d ", has[i]); printf("\n"); build(1, cnt-1, 1); //` debug(1, cnt-1, 1); for(int i = 0; i < q; ++i) { update(Q[i][2], Q[i][0], Q[i][1], 1, cnt-1, 1); printf("%d\n", sum[1]); // debug(1, cnt-1, 1); } } return 0;}
转载于:https://www.cnblogs.com/Basasuya/p/8433682.html