关于木马
  • 板块灌水区
  • 楼主Karry5307Rikka
  • 当前回复7
  • 已保存回复7
  • 发布时间2020/7/23 23:54
  • 上次更新2023/11/6 22:27:29
查看原帖
关于木马
60990
Karry5307Rikka楼主2020/7/23 23:54
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=4e5+51; 
const li inf=0x3f3f3f3f3f3f3f3f;
struct Segment{
	ll l,r,v;
	inline bool operator <(const Segment &rhs)const
	{
		return this->l<rhs.l;
	}
};
struct SegmentTree{
	ll l,r;
	li mn,mn2,tag;
}; 
Segment seg[MAXN];
SegmentTree tree[MAXN<<2];
ll n,m,ul,vl;
li res;
ll u[MAXN],v[MAXN],ux[MAXN],vx[MAXN],l[MAXN],r[MAXN];
li s[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
#define ls node<<1
#define rs (node<<1)|1
inline void update(ll node)
{
	tree[node].mn=min(tree[ls].mn,tree[rs].mn);
	tree[node].mn2=min(tree[ls].mn2,tree[rs].mn2);
}
inline void create(ll l,ll r,ll node)
{
	tree[node].l=l,tree[node].r=r;
	if(l==r)
	{
		tree[node].mn2=(tree[node].mn=l?inf:0)-s[l];
		return;
	}
	ll mid=(l+r)>>1;
	create(l,mid,ls),create(mid+1,r,rs),update(node);
}
inline void spread(ll node)
{
	ll v;
	if(v=tree[node].tag)
	{
		tree[ls].mn+=v,tree[ls].mn2+=v,tree[ls].tag+=v;
		tree[rs].mn+=v,tree[rs].mn2+=v,tree[rs].tag+=v,tree[node].tag=0;
	}
}
inline void change(ll pos,li val,ll node)
{
	if(tree[node].l==tree[node].r)
	{
		if(tree[node].mn>val)
		{
			tree[node].mn2=(tree[node].mn=val)-s[tree[node].l];
		}
		return;
	}
	spread(node);
	ll mid=(tree[node].l+tree[node].r)>>1;
	change(pos,val,pos<=mid?ls:rs),update(node);
}
inline void add(ll l,ll r,li val,ll node)
{
	if(l<=tree[node].l&&r>=tree[node].r)
	{
		tree[node].mn+=val,tree[node].mn2+=val,tree[node].tag+=val;
		return;
	}
	ll mid=(tree[node].l+tree[node].r)>>1;
	l<=mid?add(l,r,val,ls):(void)1,r>mid?add(l,r,val,rs):(void)1,update(node);
}
inline li query(ll l,ll r,ll node)
{
	if(l<=tree[node].l&&r>=tree[node].r)
	{
		return tree[node].mn;
	}
	ll mid=(tree[node].l+tree[node].r)>>1;
	return min(l<=mid?query(l,r,ls):inf,r>mid?query(l,r,rs):inf);
}
inline li query2(ll l,ll r,ll node)
{
	if(l<=tree[node].l&&r>=tree[node].r)
	{
		return tree[node].mn2;
	}
	ll mid=(tree[node].l+tree[node].r)>>1;
	return min(l<=mid?query2(l,r,ls):inf,r>mid?query2(l,r,rs):inf);
}
#undef ls
#undef rs
inline li calc(ll *u,ll *v,ll ul,ll vl)
{
	li mn,mn2;
	for(register int i=1;i<=vl;i++)
	{
		s[i]=s[i-1]+v[i];
	}
	for(register int i=1;i<=ul;i++)
	{
		seg[i]=(Segment){l[i],r[i],u[i]};
	}
	sort(seg+1,seg+ul+1),create(0,vl,1);
	for(register int i=1;i<=ul;i++)
	{
		mn=query(0,seg[i].l-1,1)+s[seg[i].r]-s[seg[i].l-1];
		mn2=query2(seg[i].l,seg[i].r,1)+s[seg[i].r];
		add(0,seg[i].r-1,seg[i].v,1),change(seg[i].r,min(mn,mn2),1);
		cout<<seg[i].l<<" "<<seg[i].r<<endl;
	}
	return tree[1].mn;
}
int main()
{
	n=read(),m=read();
	for(register int i=1;i<=n+m-1;i++)
	{
		v[i]=read();
	}
	for(register int i=1;i<=n+m-1;i++)
	{
		u[i]=read();
	}
	for(register int i=1;i<=n+m-1;i+=2)
	{
		ux[++ul]=u[i];
	}
	for(register int i=1;i<=n+m-1;i++)
	{
		!(m-i&1)?vx[++vl]=v[i]:1;
	}
	l[1]=r[1]=(m+1)>>1;
	for(register int i=2;i<=ul;i++)
	{
		r[i]=r[i-1]+((i-1)*2-1>=n?-1:((i-1)*2-1==n-1?0:1));
		l[i]=r[i]=min(min(n,m),min((i<<1)-1,n+m-(i<<1)+1))+1;
	}
	res+=calc(ux,vx,ul,vl),ul=vl=0;
	for(register int i=1;i<=n+m-1;i+=2)
	{
		ux[++ul]=u[i];
	}
	for(register int i=1;i<=n+m-1;i++)
	{
		(m-i&1)?vx[++vl]=v[i]:1;
	}
	l[1]=max(1,m>>1),r[1]=(m>>1)+min(n-1,1);
	for(register int i=2;i<=ul;i++)
	{
		r[i]=r[i-1]+((i-1)*2>=n?-1:((i-1)*2==n-1?0:1));
		l[i]=r[i]=min(min(n,m),min(i<<1,n+m-(i<<1)))+1;
	}
	printf("%lld\n",res+calc(ux,vx,ul,vl));
}

当我运行这段程序的时候说是调用了 WerFault.exe 但是这里面没有任何调用啊究竟是啥回事啊

2020/7/23 23:54
加载中...