妈的调了两天终于过了... 我好菜啊.
题意
对长度为 n 的序列执行 q 种操作,
0: 把区间内的值都置为 0;
1: 把区间内的值都置为 1;
2: 把区间内的 0 都置为 1, 区间内的 1 都置为 0;
3: 查询区间里 1 的个数;
4: 查询区间里最长的连续为 1 的区间的长度;
题解
显然, 线段树区间更新区间查询可解此题, 具体是:
维护懒标标记 set, 区间里 1 的个数 sum1, 区间左端点 l, 区间右端点 r, 区间里最长的连续为 1 的区间的长度 sub, 区间里最长的连续为 0 的区间的长度 zsub, 区间里以左端点为起点的连续为 1 的区间的长度 lsub1, 区间里以左端点为起点的连续为 0 的区间的长度 lsub0, 区间里以又端点为起点的连续为 1 的区间的长度 rsub1, 区间里以右端点为起点的连续为 0 的区间的长度 rsub0, 区间里以左端点为起点的连续为 1 的区间的长度 lsub1. 把这十个给维护好就行了呀.
- #define dbg(x) cout <<#x << "=" << (x) << endl#define IO std: :iOS: :sync_with_stdio(0);#include < bits / stdc++.h> #define iter: :iterator using namespace std;
- typedef long long ll;
- typedef pair <ll,
- ll> P;#define pb push_back#define se second#define fi first#define rs o <<1 | 1#define ls o << 1 const ll inf = 0x7fffffff;
- const int N = 1e5 + 10;
- struct node {
- int sum1,
- lsub0,
- lsub1,
- rsub0,
- rsub1;
- int l,
- r,
- sub,
- zsub;
- int set;
- }
- a[N * 4];
- void push(int o, int l, int r) {
- int g = r - l + 1;
- int gl = a[ls].r - a[ls].l + 1;
- int gr = a[rs].r - a[rs].l + 1;
- a[o].sum1 = a[ls].sum1 + a[rs].sum1;
- a[o].lsub0 = a[ls].lsub0;
- a[o].rsub0 = a[rs].rsub0;
- if (a[o].lsub0 == gl) {
- a[o].lsub0 += a[rs].lsub0;
- }
- if (a[o].rsub0 == gr) {
- a[o].rsub0 += a[ls].rsub0;
- }
- a[o].lsub1 = a[ls].lsub1;
- a[o].rsub1 = a[rs].rsub1;
- if (a[o].lsub1 == gl) {
- a[o].lsub1 += a[rs].lsub1;
- }
- if (a[o].rsub1 == gr) {
- a[o].rsub1 += a[ls].rsub1;
- }
- a[o].sub = max(a[ls].rsub1 + a[rs].lsub1, max(a[ls].sub, a[rs].sub));
- a[o].zsub = max(a[ls].rsub0 + a[rs].lsub0, max(a[ls].zsub, a[rs].zsub));
- }
- void sw(int o, int l, int r) {
- int g = r - l + 1;
- a[o].set = 1 - a[o].set;
- a[o].sum1 = g - a[o].sum1;
- swap(a[o].lsub0, a[o].lsub1);
- swap(a[o].rsub0, a[o].rsub1);
- swap(a[o].sub, a[o].zsub);
- }
- void down(int o, int l, int r) {
- int g = r - l + 1;
- int gl = a[ls].r - a[ls].l + 1;
- int gr = a[rs].r - a[rs].l + 1;
- int x = a[o].set;
- if (x == -1) return;
- if (x < 2) {
- a[ls].set = a[rs].set = x;
- a[ls].lsub1 = a[ls].rsub1 = a[ls].sum1 = a[ls].sub = x ? gl: 0;
- a[rs].lsub1 = a[rs].rsub1 = a[rs].sum1 = a[rs].sub = x ? gr: 0;
- a[ls].lsub0 = a[ls].rsub0 = a[ls].zsub = x ? 0 : gl;
- a[rs].lsub0 = a[rs].rsub0 = a[rs].zsub = x ? 0 : gr;
- a[o].set = -1;
- } else {
- a[o].set = -1;
- int m = (l + r) / 2;
- sw(ls, l, m);
- sw(rs, m + 1, r);
- }
- }
- void build(int o, int l, int r) {
- a[o].set = -1;
- if (l == r) {
- int x;
- scanf("%d", &x);
- a[o].l = a[o].r = l;
- a[o].sum1 = a[o].lsub1 = a[o].rsub1 = a[o].sub = x;
- a[o].lsub0 = a[o].rsub0 = a[o].zsub = 1 - x;
- return;
- }
- int m = (l + r) / 2;
- build(ls, l, m);
- build(rs, m + 1, r);
- a[o].l = a[ls].l;
- a[o].r = a[rs].r;
- push(o, l, r);
- }
- void up(int o, int l, int r, int ql, int qr, int k) {
- int g = r - l + 1;
- int gl = a[ls].r - a[ls].l + 1;
- int gr = a[rs].r - a[rs].l + 1;
- if (l>= ql && r <= qr) {
- if (k <2) {
- a[o].set = k;
- a[o].lsub1 = a[o].rsub1 = a[o].sub = a[o].sum1 = k ? g: 0;
- a[o].lsub0 = a[o].rsub0 = a[o].zsub = k ? 0 : g;
- } else sw(o, l, r);
- return;
- }
- down(o, l, r);
- int m = (l + r) / 2;
- if (ql <= m) up(ls, l, m, ql, qr, k);
- if (qr> m) up(rs, m + 1, r, ql, qr, k);
- push(o, l, r);
- }
- int qu(int o, int l, int r, int ql, int qr, int k) {
- if (k == 3) {
- if (l>= ql && r <= qr) {
- return a[o].sum1;
- }
- down(o, l, r);
- int m = (l + r) / 2;
- int res = 0;
- if (ql <= m) res += qu(ls, l, m, ql, qr, k);
- if (qr> m) res += qu(rs, m + 1, r, ql, qr, k);
- return res;
- }
- if (l>= ql && r <= qr) {
- return a[o].sub;
- }
- down(o, l, r);
- int m = (l + r) / 2;
- int res = min(a[ls].rsub1, m - ql + 1) + min(a[rs].lsub1, qr - m);
- if (ql <= m) res = max(res, qu(ls, l, m, ql, qr, k));
- if (qr> m) res = max(res, qu(rs, m + 1, r, ql, qr, k));
- return res;
- }
- int T,
- n,
- q;
- int main() {
- scanf("%d", &T);
- while (T--) {
- scanf("%d%d", &n, &q);
- build(1, 1, n);
- while (q--) {
- int k,
- l,
- r;
- scanf("%d%d%d", &k, &l, &r);
- l++;
- r++;
- if (k <= 2) up(1, 1, n, l, r, k);
- else printf("%d\n", qu(1, 1, n, l, r, k));
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3013371.html