题目链接: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的个数
解题思路:区间合并+成段更新。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005;
int N, M, a[maxn];
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
struct Node {
int l, r, filp, set;
int lc[2], rc[2], sc[2];
int cnt[2];
int length() {
return r - l + 1;
}
void maintain(int d) {
set = d;
filp = 0;
for (int i = 0; i < 2; i++)
lc[i] = rc[i] = sc[i] = cnt[i] = (i == d ? r - l + 1 : 0);
}
void splay() {
if (set != -1)
set ^= 1;
else
filp ^= 1;
swap(lc[0], lc[1]);
swap(rc[0], rc[1]);
swap(sc[0], sc[1]);
swap(cnt[0], cnt[1]);
}
}nd[maxn << 2];
void pushup(int u) {
for (int i = 0; i < 2; i++) {
nd[u].cnt[i] = nd[lson(u)].cnt[i] + nd[rson(u)].cnt[i];
nd[u].lc[i] = nd[lson(u)].lc[i] + (nd[lson(u)].lc[i] == nd[lson(u)].length() ? nd[rson(u)].lc[i] : 0);
nd[u].rc[i] = nd[rson(u)].rc[i] + (nd[rson(u)].rc[i] == nd[rson(u)].length() ? nd[lson(u)].rc[i] : 0);
nd[u].sc[i] = max(max(nd[lson(u)].sc[i], nd[rson(u)].sc[i]), nd[lson(u)].rc[i] + nd[rson(u)].lc[i]);
}
}
void pushdown (int u) {
if (nd[u].filp) {
nd[lson(u)].splay();
nd[rson(u)].splay();
nd[u].filp = 0;
} else if (nd[u].set != -1) {
nd[lson(u)].maintain(nd[u].set);
nd[rson(u)].maintain(nd[u].set);
nd[u].set = -1;
}
}
void build(int u, int l, int r) {
nd[u].l = l, nd[u].r = r;
nd[u].filp = 0, nd[u].set = -1;
if (l == r) {
nd[u].maintain(a[l]);
return;
}
int mid = (l + r) / 2;
build(lson(u), l, mid);
build(rson(u), mid + 1, r);
pushup(u);
}
void modify (int u, int l, int r, int v) {
if (l <= nd[u].l && nd[u].r <= r) {
nd[u].maintain(v);
return;
}
pushdown(u);
int mid = (nd[u].l + nd[u].r) / 2;
if (l <= mid)
modify(lson(u), l, r, v);
if (r > mid)
modify(rson(u), l, r, v);
pushup(u);
}
void modify (int u, int l, int r) {
if (l <= nd[u].l && nd[u].r <= r) {
nd[u].splay();
return;
}
pushdown(u);
int mid = (nd[u].l + nd[u].r) / 2;
if (l <= mid)
modify(lson(u), l, r);
if (r > mid)
modify(rson(u), l, r);
pushup(u);
}
int query_cnt(int u, int l, int r) {
if (l <= nd[u].l && nd[u].r <= r)
return nd[u].cnt[1];
pushdown(u);
int mid = (nd[u].l + nd[u].r) / 2, ret = 0;
if (l <= mid)
ret += query_cnt(lson(u), l, r);
if (r > mid)
ret += query_cnt(rson(u), l, r);
pushup(u);
return ret;
}
int query_len(int u, int l, int r) {
if (l <= nd[u].l && nd[u].r <= r)
return nd[u].sc[1];
pushdown(u);
int mid = (nd[u].l + nd[u].r) / 2, ret;
if (r <= mid)
ret = query_len(lson(u), l, r);
else if (l > mid)
ret = query_len(rson(u), l, r);
else {
int ll = query_len(lson(u), l, r);
int rr = query_len(rson(u), l, r);
int A = min(nd[lson(u)].rc[1], mid - l + 1);
int B = min(nd[rson(u)].lc[1], r - mid);
ret = max(max(ll, rr), A + B);
}
pushup(u);
return ret;
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
scanf("%d%d", &N, &M);
for (int i = 0; i < N; i++)
scanf("%d", &a[i]);
build(1, 0, N - 1);
int op, l, r;
while (M--) {
scanf("%d%d%d", &op, &l, &r);
if (op == 0)
modify(1, l, r, 0);
else if (op == 1)
modify(1, l, r, 1);
else if (op == 2)
modify(1, l, r);
else if (op == 3)
printf("%d\n", query_cnt(1, l, r));
else
printf("%d\n", query_len(1, l, r));
}
}
return 0;
}
分享到:
相关推荐
hdu 1166线段树代码
hdu 1166线段树
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
NULL 博文链接:https://128kj.iteye.com/blog/1738772
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
题面 【题目描述】 有nnn个营地,已知每个营地的人数,有四条命令: (1)Add(1) Add(1)Add iii jjj,iii和jjj为正整数,表示第iii个营地增加jjj个人(jjj不超过303030) (2)Sub(2)Sub(2)Sub iii jjj ,iii和jjj为正...
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
http://acm.hdu.edu.cn/showproblem.php?pid=5667 题目分析 像这种递推公式的问题,n很大的时候,常用的处理方法是矩阵快速幂,但是这个好像很难构造。 博主思路如下:取对数 设k(i) = loga(f(i)) 那么 根据推导 k...