HDU 3397 Sequence operation(线段树)
2024-10-12 09:30:48
HDU 3397 Sequence operation
题意:给定一个01序列,有5种操作
0 a b [a.b]区间置为0
1 a b [a,b]区间置为1
2 a b [a,b]区间0变成1,1变成0
3 a b 查询[a,b]区间1的个数
4 a b 查询[a,b]区间连续1最长的长度
思路:线段树线段合并。须要两个延迟标记一个置为01,一个翻转,然后因为4操作,须要记录左边最长0、1。右边最长0、1,区间最长0、1,然后区间合并去搞就可以
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define lson(x) ((x<<1)+1)
#define rson(x) ((x<<1)+2)
const int N = 100005; int t, n, m; struct Node {
int l, r, sum[3][2], num;
int setv, flip;
Node() {
setv = -1;
flip = 0;
}
int size() {return r - l + 1;}
void gao1(int v) {
setv = v;
num = v * (r - l + 1);
for (int i = 0; i < 3; i++) {
sum[i][v] = r - l + 1;
sum[i][!v] = 0;
}
flip = 0;
}
void gao2() {
flip ^= 1;
for (int i = 0; i < 3; i++)
swap(sum[i][0], sum[i][1]);
num = r - l + 1 - num;
}
} node[N * 4]; Node merge(Node lson, Node rson) {
Node x;
x.l = lson.l; x.r = rson.r;
for (int i = 0; i < 2; i++) {
x.sum[0][i] = lson.sum[0][i];
x.sum[1][i] = rson.sum[1][i];
x.sum[2][i] = max(lson.sum[2][i], rson.sum[2][i]);
if (lson.sum[0][i] == lson.size())
x.sum[0][i] += rson.sum[0][i];
if (rson.sum[1][i] == rson.size())
x.sum[1][i] += lson.sum[1][i];
x.sum[2][i] = max(x.sum[2][i], lson.sum[1][i] + rson.sum[0][i]);
}
x.num = lson.num + rson.num;
return x;
} void pushup(int x) {
node[x] = merge(node[lson(x)], node[rson(x)]);
} void pushdown(int x) {
if (node[x].setv != -1) {
node[lson(x)].gao1(node[x].setv);
node[rson(x)].gao1(node[x].setv);
node[x].setv = -1;
}
if (node[x].flip) {
node[lson(x)].gao2();
node[rson(x)].gao2();
node[x].flip = 0;
}
} void build(int l, int r, int x = 0) {
node[x].l = l; node[x].r = r;
node[x].setv = -1; node[x].flip = 0;
if (l == r) {
int tmp;
scanf("%d", &tmp);
for (int i = 0; i < 3; i++) {
node[x].sum[i][tmp] = 1;
node[x].sum[i][!tmp] = 0;
}
node[x].num = tmp;
return;
}
int mid = (l + r) / 2;
build(l, mid, lson(x));
build(mid + 1, r, rson(x));
pushup(x);
} void add(int l, int r, int v, int x = 0) {
if (node[x].l >= l && node[x].r <= r) {
if (v == 2) node[x].gao2();
else node[x].gao1(v);
return;
}
int mid = (node[x].l + node[x].r) / 2;
pushdown(x);
if (l <= mid) add(l, r, v, lson(x));
if (r > mid) add(l, r, v, rson(x));
pushup(x);
} Node query(int l, int r, int x = 0) {
if (node[x].l >= l && node[x].r <= r)
return node[x];
int mid = (node[x].l + node[x].r) / 2;
pushdown(x);
Node ans;
if (l <= mid && r > mid) ans = merge(query(l, r, lson(x)), query(l, r, rson(x)));
else if (l <= mid) ans = query(l, r, lson(x));
else if (r > mid) ans = query(l, r, rson(x));
pushup(x);
return ans;
} int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
build(0, n - 1);
int op, a, b;
while (m--) {
scanf("%d%d%d", &op, &a, &b);
if (op <= 2) add(a, b, op);
else if (op == 3) printf("%d\n", query(a, b).num);
else if (op == 4) printf("%d\n", query(a, b).sum[2][1]);
}
}
return 0;
}
最新文章
- ios app架构设计系统文章
- 服务器bonding
- 【微信平台&;后台管理】第一个外包项目:XX科技城微信平台项目总结
- C++获取系统的Mac地址
- [bzoj3196][Tyvj 1730][二逼平衡树] (线段树套treap)
- Ubuntu 16.04 升级 PHP 版本至 7.1
- nyoj 聪明的kk
- polaris: session和middleware的支持
- 如何让浏览器支持ES6语法,步骤详细到小学生都能看懂!
- sprd测试系统跑vts
- swift 实践- 05 -- UITextField
- vue-router中query和params传参(接收参数)以及$router、$route的区别
- titlesplit
- Leetcode 980. 不同路径 III
- Django商城项目笔记No.1项目准备工作
- Linux 正则
- Kettle7.1在window启动报错
- 获取assets文件内容,raw内容
- 假·最大子段和 (sdutoj 4359 首尾相连)(思维)
- js + -操作符
热门文章
- DescribingDesign Patterns 描述设计模式
- javascript (string 部分)
- eclipse+tomcat+maven debug的时候总是出现source not found /Edit lookup path...的问题解决方案
- QTableWidget的用法总结
- C++编译时函数名修饰约定规则(很具体),MFC提供的宏,extern ";C";的作用
- jquery 单击li防止重复加载的实现代码
- php __autoload使用
- 《白手起家Win32SDK应用程序》(完整版+目录)
- Eclipse下执行main函数报java.lang.NoClassDefFoundError的解决
- UVA 10603 Fill(正确代码尽管非常搓,网上很多代码都不能AC)