题目：https://loj.ac/problem/2551
答案是排序后依次走到 K ~ K+r-l 。
想维护一个区间排序后的结果，使得可以在上面二分、求和；二分可以知道贡献是正还是负。
于是想用树套树维护一段区间的元素减去从0开始的等差数列的值。为了二分，维护 fr , sc 表示权值区间里第一个/最后一个权值。
时间空间都是 nlog2n 的，空间连 70 分的范围都开不下。而且对拍1000以内的数据还有错误，交上去 TLE 得只能得 70 分。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define ls Ls[cr]
#define rs Rs[cr]
using namespace std;
int rdn()
{
int ret=0;bool fx=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
return fx?ret:-ret;
}
int Mx(int a,int b){return a>b?a:b;}
int Mn(int a,int b){return a<b?a:b;}
ll Abs(ll x){if(x<0)x=-x;return x;}
const int N=1e5+5,M=N<<1,M2=N*180;
int n,m,qk,fx,a[N],tp[N],tot,Ls[M],Rs[M],rt[M];
struct Node{
int ct,fr,sc;ll sm;
Node(int c=0,ll s=0,int fr=N,int sc=0)://fr:mn,sc:mx
ct(c),sm(s),fr(fr),sc(sc) {}
Node operator+ (const Node &b)const
{return Node(ct+b.ct,sm+b.sm,Mn(fr,b.fr),Mx(sc,b.sc));}
}I;
ll cal(int fx,int ct){return (ll)(2*fx-ct+1)*ct/2;}
namespace G{
int tot,Ls[M2],Rs[M2]; Node vl[M2];
void ins(int l,int r,int &cr,int p,int k)
{
if(!cr){cr=++tot; vl[cr]=I;}
vl[cr].sm+=tp[k]; vl[cr].ct++;
vl[cr].fr=Mn(vl[cr].fr,k); vl[cr].sc=Mx(vl[cr].sc,k);
if(l==r)return; int mid=l+r>>1;
if(p<=mid)ins(l,mid,ls,p,k);
else ins(mid+1,r,rs,p,k);
}
Node qry(int l,int r,int cr,int L,int R)
{
if(!cr)return I; if(l>=L&&r<=R)return vl[cr];
int mid=l+r>>1;
if(mid<L)return qry(mid+1,r,rs,L,R);
if(R<=mid)return qry(l,mid,ls,L,R);
return qry(l,mid,ls,L,R)+qry(mid+1,r,rs,L,R);
}
}
void build(int l,int r,int cr)
{
if(l==r)return; int mid=l+r>>1;
ls=++tot; build(l,mid,ls);
rs=++tot; build(mid+1,r,rs);
}
void ins(int l,int r,int cr,int p,int p2)
{
G::ins(1,n,rt[cr],p2,p);
if(l==r)return; int mid=l+r>>1;
if(p<=mid)ins(l,mid,ls,p,p2);
else ins(mid+1,r,rs,p,p2);
}
ll qry(int l,int r,int cr,int L,int R)
{
Node d=G::qry(1,n,rt[cr],L,R);
if(!d.ct)return 0;
int fr=tp[d.fr]+fx, sc=tp[d.sc]+(fx-d.ct+1);
if((fr>=qk&&sc>=qk)||(fr<=qk&&sc<=qk))
{
ll ret=d.sm+cal(fx,d.ct),tmp=(ll)d.ct*qk;
fx-=d.ct;
return Abs(ret-tmp);
}
int mid=l+r>>1;
return qry(l,mid,ls,L,R)+qry(mid+1,r,rs,L,R);
}
int main()
{
n=rdn();m=rdn();
for(int i=1;i<=n;i++)a[i]=tp[i]=rdn();
sort(tp+1,tp+n+1); int lm=unique(tp+1,tp+n+1)-tp-1;
tot=1;build(1,n,1);
for(int i=1;i<=n;i++)
{
a[i]=lower_bound(tp+1,tp+lm+1,a[i])-tp;
ins(1,n,1,a[i],i);
}
for(int i=1,l,r;i<=m;i++)
{
l=rdn();r=rdn();qk=rdn(); fx=0;
printf("%lld\n",qry(1,n,1,l,r));
}
return 0;
}
View Code
看题解发现不用树套树，用主席树即可。
在主席树上二分，无法维护 fr , sc 表示权值区间里第一个/最后一个权值。
又看题解，发现可以维护区间里元素个数 ct，只要看看 ct[ ls ] 和 mid-K+1 哪个大，就知道该往哪边走。此时可以把另一个孩子里的元素都贡献给答案。
log(1e6)=20 ，但空间开 N*20 不够。开 N*21 可以。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define ls Ls[cr]
#define rs Rs[cr]
using namespace std;
int rdn()
{
int ret=0;bool fx=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
return fx?ret:-ret;
}
int Mx(int a,int b){return a>b?a:b;}
const int N=5e5+5,M=N*21;
int n,m,a[N],tp[N],mx,k,rt[N]; ll ans;
int tot,Ls[M],Rs[M],ct[M];ll sm[M];
ll cal(int x,int c){return (2ll*x+c-1)*c/2;}
void ins(int l,int r,int &cr,int pr,int p)
{
cr=++tot; ls=Ls[pr];rs=Rs[pr];
ct[cr]=ct[pr]+1; sm[cr]=sm[pr]+p;
if(l==r)return; int mid=l+r>>1;
if(p<=mid)ins(l,mid,ls,Ls[pr],p);
else ins(mid+1,r,rs,Rs[pr],p);
}
void qry(int l,int r,int cr,int pr)
{
if(!(ct[cr]-ct[pr]))return;
if(l==r){ans+=abs(sm[cr]-k);return;}
int mid=l+r>>1;
int lc=ct[ls]-ct[Ls[pr]],rc=ct[rs]-ct[Rs[pr]];
if(lc<=mid-k+1)
{
ans+=sm[rs]-sm[Rs[pr]]-cal(k+lc,rc);
qry(l,mid,ls,Ls[pr]);
}
else
{
ans+=cal(k,lc)-sm[ls]+sm[Ls[pr]]; k+=lc;
qry(mid+1,r,rs,Rs[pr]);
}
}
int main()
{
n=rdn();m=rdn();
for(int i=1;i<=n;i++) a[i]=rdn(),mx=Mx(mx,a[i]);
for(int i=1;i<=n;i++)
ins(1,mx,rt[i],rt[i-1],a[i]);
for(int i=1,l,r;i<=m;i++)
{
l=rdn();r=rdn();k=rdn();
ans=0; qry(1,mx,rt[r],rt[l-1]);
printf("%lld\n",ans);
}
return 0;
}