resftlmuttmotw @ 2019-11-05 13:26:03
P2572 [SCOI2010]序列操作
样例
5
2
6
5我的输出是
5
2
6
7#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= x&&x <= '9')
template<typename T>
inline T Read(T Type)
{
T x = 0,f = 1;
char a = getchar();
while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
return x * f;
}
//快读
const int MAXN = 100010;
struct segment_tree
{
struct node
{
int len,sum,lazy,rev,lsum[2],rsum[2],maxl[2];
}tree[MAXN << 2];
void update(int k,int k1,int k2,int lenl,int lenr,int x)//标记下传后(k1,k2)修改k
{
tree[k].maxl[x] = max(tree[k1].maxl[x],max(tree[k2].maxl[x],tree[k1].rsum[x] + tree[k2].lsum[x]));
tree[k].lsum[x] = tree[k1].lsum[x];
if(tree[k1].lsum[x] == lenl) tree[k].lsum[x] += tree[k2].lsum[x];
tree[k].rsum[x] = tree[k2].rsum[x];
if(tree[k2].rsum[x] == lenr) tree[k].rsum[x] += tree[k1].rsum[x];
tree[k].sum = tree[k1].sum + tree[k2].sum;
}
void build(int k,int l,int r)//建树
{
if(l == r)
{
int x = tree[k].sum = Read(1);
tree[k].maxl[x] = tree[k].lsum[x] = tree[k].rsum[x] = 1;
tree[k].maxl[!x] = tree[k].lsum[!x] = tree[k].rsum[!x] = 0;
tree[k].lazy = -1,tree[k].rev = 0;
return;
}
int mid = l + r >> 1;
tree[k].lazy = -1,tree[k].rev = 0;
build(k << 1,l,mid);
build(k << 1 | 1,mid + 1,r);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,0);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,1);
}
void pushdown(int k,int k1,int len)//标记下传
{
if(tree[k].lazy != -1)
{
int x = tree[k].lazy;
tree[k1].lazy = x;
tree[k1].sum = (x == 1?len:0);
tree[k1].maxl[x] = tree[k1].lsum[x] = tree[k1].rsum[x] = len;
tree[k1].maxl[!x] = tree[k1].lsum[!x] = tree[k1].rsum[!x] = 0;
}
if(tree[k].rev)
{
tree[k1].rev = !tree[k1].rev;
tree[k1].sum = len - tree[k1].sum;
swap(tree[k1].lsum[0],tree[k1].lsum[1]);
swap(tree[k1].rsum[0],tree[k1].rsum[1]);
swap(tree[k1].maxl[0],tree[k1].maxl[1]);
}
}
void change(int k,int l,int r,int L,int R,int x)//[L,R]改x
{
if(L <= l&&r <= R)
{
tree[k].lazy = x;
tree[k].sum = (x == 1?r - l + 1:0);
tree[k].maxl[x] = tree[k].lsum[x] = tree[k].rsum[x] = r - l + 1;
tree[k].maxl[!x] = tree[k].lsum[!x] = tree[k].rsum[!x] = 0;
return;
}
int mid = l + r >> 1;
pushdown(k,k << 1,mid - l + 1);
pushdown(k,k << 1 | 1,r - mid + 1);
tree[k].lazy = -1,tree[k].rev = 0;
if(L <= mid) change(k << 1,l,mid,L,R,x);
if(mid < R) change(k << 1 | 1,mid + 1,r,L,R,x);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,0);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,1);
}
void inverse(int k,int l,int r,int L,int R)//反转
{
if(L <= l&&r <= R)
{
tree[k].rev = !tree[k].rev;
tree[k].sum = r - l + 1 - tree[k].sum;
swap(tree[k].lsum[0],tree[k].lsum[1]);
swap(tree[k].rsum[0],tree[k].rsum[1]);
swap(tree[k].maxl[0],tree[k].maxl[1]);
return;
}
int mid = l + r >> 1;
pushdown(k,k << 1,mid - l + 1);
pushdown(k,k << 1 | 1,r - mid + 1);
tree[k].lazy = -1,tree[k].rev = 0;
if(L <= mid) inverse(k << 1,l,mid,L,R);
if(mid < R) inverse(k << 1 | 1,mid + 1,r,L,R);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,0);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,1);
}
int query(int k,int l,int r,int L,int R)//1的个数
{
if(L <= l&&r <= R) return tree[k].sum;
int mid = l + r >> 1;
pushdown(k,k << 1,mid - l + 1);
pushdown(k,k << 1 | 1,r - mid + 1);
tree[k].lazy = -1,tree[k].rev = 0;
int ans = 0;
if(L <= mid) ans = query(k << 1,l,mid,L,R);
if(mid < R) ans += query(k << 1 | 1,mid + 1,r,L,R);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,0);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,1);
return ans;
}
node Sum(int k,int l,int r,int L,int R)//连续一的个数
{
if(L <= l&&r <= R)
{
tree[k].len = r - l + 1;
return tree[k];
}
int mid = l + r >> 1;
pushdown(k,k << 1,mid - l + 1);
pushdown(k,k << 1 | 1,r - mid + 1);
tree[k].lazy = -1,tree[k].rev = 0;
node k1[2];
memset(k1,0,sizeof(k1));
if(L <= mid) k1[0] = Sum(k << 1,l,mid,L,R);
if(mid < R) k1[1] = Sum(k << 1 | 1,mid + 1,r,L,R);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,0);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid + 1,1);
node k3;
k3.maxl[1] = max(k1[0].maxl[1],max(k1[1].maxl[1],k1[0].rsum[1] + k1[1].lsum[1]));
k3.lsum[1] = k1[0].lsum[1];
if(k1[0].lsum[1] == k1[0].len) k3.lsum[1] += k1[1].lsum[1];
k3.rsum[1] = k1[1].rsum[1];
if(k1[1].rsum[1] == k1[1].len) k3.rsum[1] += k1[0].rsum[1];
return k3;
}
}T;
//线段树
int main()
{
int n = Read(1),m = Read(1);
memset(T.tree,0,sizeof(T.tree));
T.build(1,1,n);
while(m--)
{
int ans,op = Read(1),l = Read(1) + 1,r = Read(1) + 1;
switch(op)
{
case 0: T.change(1,1,n,l,r,0); break;//改0
case 1: T.change(1,1,n,l,r,1); break;//改1
case 2: T.inverse(1,1,n,l,r); break;//反转
case 3: ans = T.query(1,1,n,l,r); printf("%d\n",ans); break;//1的个数
case 4: ans = T.Sum(1,1,n,l,r).maxl[1]; printf("%d\n",ans); break;//连续1的个数
}
}
return 0;
}by 览遍千秋 @ 2019-11-05 13:38:32
珂朵莉树多好
by resftlmuttmotw @ 2019-11-05 13:55:09
@expect
不会啊
现在10分了 样例过了
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= x&&x <= '9')
template<typename T>
inline T Read(T Type)
{
T x = 0,f = 1;
char a = getchar();
while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
return x * f;
}
const int MAXN = 100010;
struct segment_tree
{
struct node
{
int len,sum,lazy,rev,lsum[2],rsum[2],maxl[2];
}tree[MAXN << 2];
void update(int k,int k1,int k2,int lenl,int lenr,int x)
{
tree[k].maxl[x] = max(tree[k1].maxl[x],max(tree[k2].maxl[x],tree[k1].rsum[x] + tree[k2].lsum[x]));
tree[k].lsum[x] = tree[k1].lsum[x];
if(tree[k1].lsum[x] == lenl) tree[k].lsum[x] += tree[k2].lsum[x];
tree[k].rsum[x] = tree[k2].rsum[x];
if(tree[k2].rsum[x] == lenr) tree[k].rsum[x] += tree[k1].rsum[x];
tree[k].sum = tree[k1].sum + tree[k2].sum;
}
void build(int k,int l,int r)
{
if(l == r)
{
int x = tree[k].sum = Read(1);
tree[k].maxl[x] = tree[k].lsum[x] = tree[k].rsum[x] = 1;
tree[k].maxl[!x] = tree[k].lsum[!x] = tree[k].rsum[!x] = 0;
tree[k].lazy = -1,tree[k].rev = 0;
return;
}
int mid = l + r >> 1;
tree[k].lazy = -1,tree[k].rev = 0;
build(k << 1,l,mid);
build(k << 1 | 1,mid + 1,r);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,0);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,1);
}
void pushdown(int k,int k1,int len)
{
if(tree[k].lazy != -1)
{
int x = tree[k].lazy;
tree[k1].lazy = x;
tree[k1].sum = (x == 1?len:0);
tree[k1].maxl[x] = tree[k1].lsum[x] = tree[k1].rsum[x] = len;
tree[k1].maxl[!x] = tree[k1].lsum[!x] = tree[k1].rsum[!x] = 0;
}
if(tree[k].rev)
{
tree[k1].rev = !tree[k1].rev;
tree[k1].sum = len - tree[k1].sum;
swap(tree[k1].lsum[0],tree[k1].lsum[1]);
swap(tree[k1].rsum[0],tree[k1].rsum[1]);
swap(tree[k1].maxl[0],tree[k1].maxl[1]);
}
}
void change(int k,int l,int r,int L,int R,int x)
{
if(L <= l&&r <= R)
{
tree[k].lazy = x,tree[k].rev = 0;
tree[k].sum = (x == 1?r - l + 1:0);
tree[k].maxl[x] = tree[k].lsum[x] = tree[k].rsum[x] = r - l + 1;
tree[k].maxl[!x] = tree[k].lsum[!x] = tree[k].rsum[!x] = 0;
return;
}
int mid = l + r >> 1;
pushdown(k,k << 1,mid - l + 1);
pushdown(k,k << 1 | 1,r - mid);
tree[k].lazy = -1,tree[k].rev = 0;
if(L <= mid) change(k << 1,l,mid,L,R,x);
if(mid < R) change(k << 1 | 1,mid + 1,r,L,R,x);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,0);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,1);
}
void inverse(int k,int l,int r,int L,int R)
{
if(L <= l&&r <= R)
{
tree[k].rev = !tree[k].rev;
tree[k].sum = r - l + 1 - tree[k].sum;
swap(tree[k].lsum[0],tree[k].lsum[1]);
swap(tree[k].rsum[0],tree[k].rsum[1]);
swap(tree[k].maxl[0],tree[k].maxl[1]);
return;
}
int mid = l + r >> 1;
pushdown(k,k << 1,mid - l + 1);
pushdown(k,k << 1 | 1,r - mid);
tree[k].lazy = -1,tree[k].rev = 0;
if(L <= mid) inverse(k << 1,l,mid,L,R);
if(mid < R) inverse(k << 1 | 1,mid + 1,r,L,R);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,0);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,1);
}
int query(int k,int l,int r,int L,int R)
{
if(L <= l&&r <= R) return tree[k].sum;
int mid = l + r >> 1;
pushdown(k,k << 1,mid - l + 1);
pushdown(k,k << 1 | 1,r - mid);
tree[k].lazy = -1,tree[k].rev = 0;
int ans = 0;
if(L <= mid) ans = query(k << 1,l,mid,L,R);
if(mid < R) ans += query(k << 1 | 1,mid + 1,r,L,R);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,0);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,1);
return ans;
}
node Sum(int k,int l,int r,int L,int R)
{
if(L <= l&&r <= R)
{
tree[k].len = r - l + 1;
return tree[k];
}
int mid = l + r >> 1;
pushdown(k,k << 1,mid - l + 1);
pushdown(k,k << 1 | 1,r - mid);
tree[k].lazy = -1,tree[k].rev = 0;
node k1[2];
memset(k1,0,sizeof(k1));
if(L <= mid) k1[0] = Sum(k << 1,l,mid,L,R);
if(mid < R) k1[1] = Sum(k << 1 | 1,mid + 1,r,L,R);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,0);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,1);
node k3;
k3.maxl[1] = max(k1[0].maxl[1],max(k1[1].maxl[1],k1[0].rsum[1] + k1[1].lsum[1]));
k3.lsum[1] = k1[0].lsum[1];
if(k1[0].lsum[1] == k1[0].len) k3.lsum[1] += k1[1].lsum[1];
k3.rsum[1] = k1[1].rsum[1];
if(k1[1].rsum[1] == k1[1].len) k3.rsum[1] += k1[0].rsum[1];
return k3;
}
}T;
int main()
{
int n = Read(1),m = Read(1);
memset(T.tree,0,sizeof(T.tree));
T.build(1,1,n);
while(m--)
{
int ans,op = Read(1),l = Read(1) + 1,r = Read(1) + 1;
switch(op)
{
case 0: T.change(1,1,n,l,r,0); break;
case 1: T.change(1,1,n,l,r,1); break;
case 2: T.inverse(1,1,n,l,r); break;
case 3: ans = T.query(1,1,n,l,r); printf("%d\n",ans); break;
case 4: ans = T.Sum(1,1,n,l,r).maxl[1]; printf("%d\n",ans); break;
}
}
return 0;
}by resftlmuttmotw @ 2019-11-05 13:55:24
@expect
求助
by 览遍千秋 @ 2019-11-05 13:58:38
我没写过这题线段树版本啊qwq
by resftlmuttmotw @ 2019-11-05 13:59:28
@expect
那就只好请大佬动动手指了
by resftlmuttmotw @ 2019-11-05 14:01:22
@Panda_hu
@bellmanford
by resftlmuttmotw @ 2019-11-06 12:40:47
@小蒟蒻皮皮鱼
大佬帮康康
by resftlmuttmotw @ 2019-11-06 13:02:14
现在70分了
三个点都是该输出
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= x&&x <= '9')
template<typename T>
inline T Read(T Type)
{
T x = 0,f = 1;
char a = getchar();
while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
return x * f;
}
const int MAXN = 100010;
struct segment_tree
{
struct node
{
int len,sum,lazy,rev,lsum[2],rsum[2],maxl[2];
}tree[MAXN << 2];
void update(int k,int k1,int k2,int lenl,int lenr,int x)
{
tree[k].maxl[x] = max(tree[k1].maxl[x],max(tree[k2].maxl[x],tree[k1].rsum[x] + tree[k2].lsum[x]));
tree[k].lsum[x] = tree[k1].lsum[x];
if(tree[k1].lsum[x] == lenl) tree[k].lsum[x] += tree[k2].lsum[x];
tree[k].rsum[x] = tree[k2].rsum[x];
if(tree[k2].rsum[x] == lenr) tree[k].rsum[x] += tree[k1].rsum[x];
tree[k].sum = tree[k1].sum + tree[k2].sum;
}
void build(int k,int l,int r)
{
if(l == r)
{
int x = tree[k].sum = Read(1);
tree[k].maxl[x] = tree[k].lsum[x] = tree[k].rsum[x] = 1;
tree[k].maxl[!x] = tree[k].lsum[!x] = tree[k].rsum[!x] = 0;
tree[k].lazy = -1,tree[k].rev = 0;
return;
}
int mid = l + r >> 1;
tree[k].lazy = -1,tree[k].rev = 0;
build(k << 1,l,mid);
build(k << 1 | 1,mid + 1,r);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,0);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,1);
}
void pushdown(int k,int k1,int len)
{
if(tree[k].lazy != -1)
{
int x = tree[k].lazy;
tree[k1].rev = 0;
tree[k1].lazy = x;
tree[k1].sum = (x == 1?len:0);
tree[k1].maxl[x] = tree[k1].lsum[x] = tree[k1].rsum[x] = len;
tree[k1].maxl[!x] = tree[k1].lsum[!x] = tree[k1].rsum[!x] = 0;
}
if(tree[k].rev)
{
tree[k1].rev = !tree[k1].rev;
tree[k1].sum = len - tree[k1].sum;
swap(tree[k1].lsum[0],tree[k1].lsum[1]);
swap(tree[k1].rsum[0],tree[k1].rsum[1]);
swap(tree[k1].maxl[0],tree[k1].maxl[1]);
}
}
void change(int k,int l,int r,int L,int R,int x)
{
if(L <= l&&r <= R)
{
tree[k].lazy = x,tree[k].rev = 0;
tree[k].sum = (x == 1?r - l + 1:0);
tree[k].maxl[x] = tree[k].lsum[x] = tree[k].rsum[x] = r - l + 1;
tree[k].maxl[!x] = tree[k].lsum[!x] = tree[k].rsum[!x] = 0;
return;
}
int mid = l + r >> 1;
pushdown(k,k << 1,mid - l + 1);
pushdown(k,k << 1 | 1,r - mid);
tree[k].lazy = -1,tree[k].rev = 0;
if(L <= mid) change(k << 1,l,mid,L,R,x);
if(mid < R) change(k << 1 | 1,mid + 1,r,L,R,x);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,0);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,1);
}
void inverse(int k,int l,int r,int L,int R)
{
if(L <= l&&r <= R)
{
if(tree[k].lazy != -1) tree[k].lazy = !tree[k].lazy;
else tree[k].rev = !tree[k].rev;
tree[k].sum = r - l + 1 - tree[k].sum;
swap(tree[k].lsum[0],tree[k].lsum[1]);
swap(tree[k].rsum[0],tree[k].rsum[1]);
swap(tree[k].maxl[0],tree[k].maxl[1]);
return;
}
int mid = l + r >> 1;
pushdown(k,k << 1,mid - l + 1);
pushdown(k,k << 1 | 1,r - mid);
tree[k].lazy = -1,tree[k].rev = 0;
if(L <= mid) inverse(k << 1,l,mid,L,R);
if(mid < R) inverse(k << 1 | 1,mid + 1,r,L,R);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,0);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,1);
}
int query(int k,int l,int r,int L,int R)
{
if(L <= l&&r <= R) return tree[k].sum;
int mid = l + r >> 1;
pushdown(k,k << 1,mid - l + 1);
pushdown(k,k << 1 | 1,r - mid);
tree[k].lazy = -1,tree[k].rev = 0;
int ans = 0;
if(L <= mid) ans = query(k << 1,l,mid,L,R);
if(mid < R) ans += query(k << 1 | 1,mid + 1,r,L,R);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,0);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,1);
return ans;
}
node Sum(int k,int l,int r,int L,int R)
{
if(L <= l&&r <= R)
{
tree[k].len = r - l + 1;
return tree[k];
}
int mid = l + r >> 1;
pushdown(k,k << 1,mid - l + 1);
pushdown(k,k << 1 | 1,r - mid);
tree[k].lazy = -1,tree[k].rev = 0;
node k1[2];
memset(k1,0,sizeof(k1));
if(L <= mid) k1[0] = Sum(k << 1,l,mid,L,R);
if(mid < R) k1[1] = Sum(k << 1 | 1,mid + 1,r,L,R);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,0);
update(k,k << 1,k << 1 | 1,mid - l + 1,r - mid,1);
node k3;
k3.maxl[1] = max(k1[0].maxl[1],max(k1[1].maxl[1],k1[0].rsum[1] + k1[1].lsum[1]));
k3.lsum[1] = k1[0].lsum[1];
if(k1[0].lsum[1] == k1[0].len) k3.lsum[1] += k1[1].lsum[1];
k3.rsum[1] = k1[1].rsum[1];
if(k1[1].rsum[1] == k1[1].len) k3.rsum[1] += k1[0].rsum[1];
return k3;
}
}T;
int main()
{
int n = Read(1),m = Read(1);
memset(T.tree,0,sizeof(T.tree));
T.build(1,1,n);
while(m--)
{
int ans,op = Read(1),l = Read(1) + 1,r = Read(1) + 1;
switch(op)
{
case 0: T.change(1,1,n,l,r,0); break;
case 1: T.change(1,1,n,l,r,1); break;
case 2: T.inverse(1,1,n,l,r); break;
case 3: ans = T.query(1,1,n,l,r); printf("%d\n",ans); break;
case 4: ans = T.Sum(1,1,n,l,r).maxl[1]; printf("%d\n",ans); break;
}
}
return 0;
}by 小蒟蒻皮皮鱼 @ 2019-11-06 13:52:38
@resftlmuttmotw 你可以到前面的讨论帖子里找到一个发数据生成器的，然后拿题解和你的程序对拍一个小一点的数据（我当时是10个数4个操作），有了小数据之后就可以调试了
by resftlmuttmotw @ 2019-11-06 14:00:56
@小蒟蒻皮皮鱼
用了 随机生成了好几组 都是对的