有人能帮忙看下嘛,大致是 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("");
}
}
}