空の軌跡 @ 2019-11-01 10:41:37
加inline开O2 输出 5 2 6 5
不加inline开O2 输出 5 2 6 4
不加inline不开O2 输出 5 2 7 5
不加inline不开O2 输出 5 2 7 5
inline 是 pushup 之前的 inline
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<iomanip>
#include<map>
#include<ctime>
#include<cstdlib>
#define ls qk<<1
#define rs qk<<1|1
using namespace std;
struct date
{
int la0,la1,fi0,fi1,sum,siz,tag,lian1,lian0;
}tree[400010];
int eve[100010];
int n,m,opt,a,b;
inline date pushup(date l,date r)
{
date re;re.siz=l.siz+r.siz;
re.sum=l.sum+r.sum;
re.fi1=l.fi1;re.la1=r.la1;
re.fi0=l.fi0;re.la0=r.la0;
if(l.sum==l.siz)re.fi1+=r.fi1;
if(l.sum==0)re.fi0+=r.fi0;
if(r.sum==r.siz)re.la1+=l.la1;
if(r.sum==0)re.la0+=l.la0;
re.lian1=max(max(l.lian1,r.lian1),l.la1+r.fi1);
re.lian0=max(max(l.lian0,r.lian0),l.la0+r.fi0);
return re;
}
void build(int qk,int l,int r)
{
//cout<<"f**k: "<<qk<<" "<<tree[qk].tag<<"\n";
if(l==r)
{
if(eve[l])tree[qk].la1=tree[qk].sum=tree[qk].fi1=tree[qk].lian1=1;
else tree[qk].lian0=tree[qk].fi0=tree[qk].la0=1;
tree[qk].siz=1;
return;
}
int mid=l+r>>1;
build(ls,l,mid);build(rs,mid+1,r);
tree[qk]=pushup(tree[ls],tree[rs]);
}
void tagcnm(int qk,int l,int r,int mid);
void settag1(int qk,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
{
tree[qk].sum=tree[qk].siz;
tree[qk].lian0=tree[qk].fi0=tree[qk].la0=0;
tree[qk].lian1=tree[qk].fi1=tree[qk].la1=tree[qk].siz;
tree[qk].tag=1;
return;
}
int mid=l+r>>1;
if(tree[qk].tag)tagcnm(qk,l,r,mid);
if(x<=mid)settag1(ls,l,mid,x,y);
if(y>mid)settag1(rs,mid+1,r,x,y);
tree[qk]=pushup(tree[ls],tree[rs]);
}
void settag2(int qk,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
{
tree[qk].sum=0;
tree[qk].lian0=tree[qk].fi0=tree[qk].la0=tree[qk].siz;
tree[qk].lian1=tree[qk].fi1=tree[qk].la1=0;
tree[qk].tag=2;
return;
}
int mid=l+r>>1;
if(tree[qk].tag)tagcnm(qk,l,r,mid);
if(x<=mid)settag2(ls,l,mid,x,y);
if(y>mid)settag2(rs,mid+1,r,x,y);
tree[qk]=pushup(tree[ls],tree[rs]);
}
void settagqf(int qk,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
{
tree[qk].sum=tree[qk].siz-tree[qk].sum;
swap(tree[qk].fi0,tree[qk].fi1);
swap(tree[qk].la0,tree[qk].la1);
swap(tree[qk].lian0,tree[qk].lian1);
if(tree[qk].tag==0)tree[qk].tag=3;
else if(tree[qk].tag==1)tree[qk].tag=2;
else if(tree[qk].tag==2)tree[qk].tag=1;
else if(tree[qk].tag==3)tree[qk].tag=0;
return;
}
int mid=l+r>>1;
if(tree[qk].tag)tagcnm(qk,l,r,mid);
if(x<=mid)settagqf(ls,l,mid,x,y);
if(y>mid)settagqf(rs,mid+1,r,x,y);
tree[qk]=pushup(tree[ls],tree[rs]);
}
inline void tagcnm(int qk,int l,int r,int mid)
{
// cout<<"qk: "<<qk<<" "<<tree[qk].tag<<"\n";
if(tree[qk].tag==1)
{
settag1(ls,l,mid,l,mid);
settag1(rs,mid+1,r,mid+1,r);
tree[qk].tag=0;
}
if(tree[qk].tag==2)
{
settag2(ls,l,mid,l,mid);
settag2(rs,mid+1,r,mid+1,r);
tree[qk].tag=0;
}
if(tree[qk].tag==3)
{
settagqf(ls,l,mid,l,mid);
settagqf(rs,mid+1,r,mid+1,r);
tree[qk].tag=0;
}
}
date ask(int qk,int l,int r,int x,int y)
{
if(x<=l&&r<=y)return tree[qk];
int mid=l+r>>1;
if(tree[qk].tag)tagcnm(qk,l,r,mid);
if(x<=mid)
{
if(y>mid)return pushup(ask(ls,l,mid,x,y),ask(rs,mid+1,r,x,y));
return ask(ls,l,mid,x,y);
}
return ask(rs,mid+1,r,x,y);
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=0;i<n;i++)cin>>eve[i];
build(1,0,n-1);
while(m--)
{
//for(int i=1;i<=n;i++)cout<<ask(1,1,n,i,i).sum<<" ";
//cout<<'\n';
cin>>opt>>a>>b;
if(opt==0)settag2(1,0,n-1,a,b);
if(opt==1)settag1(1,0,n-1,a,b);
if(opt==2)settagqf(1,0,n-1,a,b);
if(opt==3)cout<<ask(1,0,n-1,a,b).sum<<'\n';
if(opt==4)cout<<ask(1,0,n-1,a,b).lian1<<'\n';
}
}
是我码风奇特,编译器有锅,系统错误,还是Windows特性?
by hly1204 @ 2019-11-01 15:07:32
您这份代码把我干傻了。。开o1和o2结果还不一样
by Hydrogen_Helium @ 2019-11-02 20:59:25
UB
by Hydrogen_Helium @ 2019-11-02 20:59:57
@空の軌跡
你的代码里有UB…………
你不死谁死……
by 空の軌跡 @ 2019-11-02 21:14:42
@hly1204 我把pushup里面的tag初始化了,估计是
by 空の軌跡 @ 2019-11-02 21:15:39
@hly1204 现在哪份代码都没问题了,虽然没初始化是我的错,但是这个不同的结果是在是很迷
by 空の軌跡 @ 2019-11-02 21:16:16
@Hydrogen_Helium 我太难了