萌新求助qwq
查看原帖
萌新求助qwq
55201
clamee楼主2020/6/16 15:05

有人能帮忙看下嘛,大致是 sol4 函数的哪里写错了。

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define int long long
il int read()
{
	int re=0,k=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')k=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){re=re*10+ch-48;ch=getchar();}
	return re*k;
}
il void write(int x)
{
	if(x<0){putchar('-');write(-x);return;}
	if(x<10)return putchar(x+48),void();
	return write(x/10),write(x%10),void();
}
#define IT set<st>::iterator 
struct st{
	int l,r;
	mutable int v;
	st(int L=0,int R=0,int V=0):l(L),r(R),v(V){}
	bool operator <(const st ot)const
	{
		return l<ot.l;
	}
};
set<st> s;
int n,m,c,tree[100005],have[105],a[100005],mx[400005];

void build(int l,int r,int k)
{
	if(l==r)
	{
		mx[k]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,k<<1);
	build(mid+1,r,k<<1|1);
	mx[k]=max(mx[k<<1],mx[k<<1|1]);
}

void update(int l,int r,int k,int x,int v)
{
	if(x>r||x<l)return;
	if(l==x&&r==x)
	{
		mx[k]=v;
		return;
	}
	int mid=(l+r)>>1;
	update(l,mid,k<<1,x,v);
	update(mid+1,r,k<<1|1,x,v);
	mx[k]=max(mx[k<<1],mx[k<<1|1]);
}

int query(int l,int r,int k,int x,int y)
{
	if(x>r||y<l)return -0x3f3f3f3f3f3f3f3f;
	if(x<=l&&y>=r)
	{
		//cerr<<"@"<<mx[k]<<endl;
		return mx[k];
	}
	int mid=(l+r)>>1;
	return max(query(l,mid,k<<1,x,y),query(mid+1,r,k<<1|1,x,y));
}

IT split(int x)
{
	IT it=s.lower_bound(st(x));
	if(it!=s.end()&&it->l==x)return it;
	--it;
	int L=it->l,R=it->r,V=it->v;
	s.erase(it);
	s.insert(st(L,x-1,V));
	return s.insert(st(x,R,V)).first;
}

void assign(int l,int r,int v)
{
	IT itr=split(r+1),itl=split(l);
	s.erase(itl,itr);
	s.insert(st(l,r,v));
}

void add(int x,int k)
{
	while(x<=n)
	{
		tree[x]+=k;
		x+=x&-x;
	}
}

int sum(int x)
{
	int re=0;
	while(x)
	{
		re+=tree[x];
		x-=x&-x;
	}
	return re;
}

int sol3(int l,int r)
{
	int ans=0x3f3f3f3f3f3f3f3f,now=0,ss=0;
	memset(have,0,sizeof(have));
	IT itr=split(r+1),itl=split(l),p1,p2;
	p1=itl;p2=itl;
	while(p2!=itr)
	{
		while(now==c)
		{
			ans=min(ans,ss);
			ss-=sum(p1->r)-sum(p1->l-1);
			have[p1->v]-=p1->r-p1->l+1;
			if(!have[p1->v]){ans=min(ans,ss+a[p1->r]);now--;}
			p1++;
		}
		ss+=sum(p2->r)-sum(p2->l-1);
	//	cerr<<p2->r<<" "<<ss<<endl;
		if(!have[p2->v])now++;
		have[p2->v]+=p2->r-p2->l+1;
	//	if(p2->v==1)
	//	{
	//		cerr<<p2->l<<" "<<p2->r<<endl;
	//	}
		p2++;
	}
	while(now==c)
	{
		ans=min(ans,ss);
		//cerr<<ans<<" "<<ss<<" "<<p1->l<<" "<<p1->r<<" "<<p1->v<<" "<<have[1]<<endl;
		ss-=sum(p1->r)-sum(p1->l-1);
		have[p1->v]-=p1->r-p1->l+1;
		if(!have[p1->v]){ans=min(ans,ss+a[p1->r]);now--;}
		p1++;
	}
	if(ans>=100000000000ll)return -1;
	return ans;
}

int sol4(int l,int r)
{
	int ans=0,ss=0;
	memset(have,0,sizeof(have));
	IT itr=split(r+1),itl=split(l),p1,p2;
	p1=itl;p2=itl;
	while(p2!=itr)
	{
		ss+=a[p2->l];
		have[p2->v]++;
		while(have[p2->v]>1)
		{
			ss-=a[p1->r];
			have[p1->v]--;
			p1++;
		}
		ans=max(ans,ss);
		if(p2->l<p2->r)
		{
			//cerr<<"!"<<" "<<p2->l<<" "<<p2->r<<endl;
			ans=max(ans,query(1,n,1,p2->l,p2->r));
			p1=p2;
			memset(have,0,sizeof(have));
			have[p2->v]=1;
			ss=a[p2->r];
		}
		p2++;
	}
	ans=max(ss,ans);
	//ans=max(ans,query(1,n,1,p2->l,p2->r));
	return ans;
}
signed main()
{
	n=read();m=read();c=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		add(i,a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		int cl=read();
		s.insert(st(i,i,cl));
	}
	build(1,n,1);
	for(int i=1;i<=m;i++)
	{
		//cerr<<i<<endl;
		int typ,l,r,v;
		typ=read();l=read();r=read();
		if(typ==1)
		{
			add(l,-a[l]);
			a[l]=r;
			add(l,r);
			update(1,n,1,l,r);
		}
		else if(typ==2)
		{
			v=read();
			assign(l,r,v);
		}
		else if(typ==3)
		{
			write(sol3(l,r));
			puts("");
		}
		else
		{
			write(sol4(l,r));
			puts("");
		}
	}
}
2020/6/16 15:05
加载中...