1 条题解

  • 0
    @ 2025-8-24 22:46:45

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar yyyyxh
    OI 是啥 (O_o)？

    搬运于2025-08-24 22:46:45，当前版本为作者最后更新于2023-11-23 09:49:05，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    发现时限这么大，考虑根号。题目相当于是对于每一个询问，你需要求出往后添加多少个询问之后有每个点的 cntcnt 数组对应位置超过 aa。可以直接序列分块，劈成一段一段后所有答案直接取个 max⁡\max 就是原答案。

    整块的话考虑离线处理出所有位置的答案，这个答案明显是有单调性的所以可以双指针。直接用线段树比较憨，发现你可以直接用分块的结构，散块的修改暴力做，整块修改直接打标记。

    散块考虑对每个位置扫描线，发现是让我们支持加入删除和查询第 kk 大，树状树组可以直接做到 O(nnlog⁡n)O(n\sqrt{n\log n})。

    但是插入删除第 kk 大这玩意也是可以根号平衡的，具体地我们再维护一个数组 mpmp 表示第 ii 大的数位于哪个块内，发现插入和删除对于这个数组的影响都是 O(n)O(\sqrt n) 的，然后再对每个块维护第 kk 大的数具体是哪个，这个数组可以暴力重构，于是就做到了 O(nn)O(n\sqrt n)，空间离线一些东西当然可以做到 O(n)O(n)。

    #include <cstdio>
#include <vector>
#include <cmath>
#include <cassert>
#include <algorithm>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=100003,B=320;
int n,m,sq,bn;
int ql[N],qr[N];
vector<int> vec[N],ui[N],ud[N],qi[N],qd[N];
int bel[N],res[N],ans[N];
int a[N],lb[B],rb[B];
int ccbase[N<<1],*cc=ccbase+N,arr[N];
namespace Block{
	int bid[N],mp[N];
	int cnt[B],pre[N];
	int f[B][B],msq;
	int mlb[N],mrb[N];
	inline void init(){
		msq=ceil(sqrt(m));
		for(int i=1;i<=m;++i) bid[i]=(i-1)/msq+1;
		for(int i=1;i<=bid[m];++i){
			mlb[i]=(i-1)*msq+1;
			mrb[i]=i*msq;
		}
		mrb[bid[m]]=m;
	}
	inline void inc(int x){
		int xx=bid[x];
		for(int i=x;i<=mrb[xx];++i) ++pre[i];
		for(int i=mrb[xx];i>=mlb[xx];--i) f[xx][pre[i]]=i;
		for(int i=bid[m];i>=xx;--i) mp[++cnt[i]]=i;
	}
	inline void dec(int x){
		int xx=bid[x];
		for(int i=x;i<=mrb[xx];++i) --pre[i];
		for(int i=mrb[xx];i>=mlb[xx];--i) f[xx][pre[i]]=i;
		for(int i=xx;i<=bid[m];++i) mp[cnt[i]--]=i+1;
		mp[cnt[bid[m]]+1]=0;
	}
	inline int qry(int x){return cnt[bid[x]-1]+pre[x];}
	inline int jump(int x){
		if(x>=N) return m+1;
		if(!mp[x]) return m+1;
		int xx=mp[x];
		x-=cnt[xx-1];
		return f[xx][x];
	}
}
bool exi[N];
int s[N],tp;
int ss[N],stp;
int main(){
	n=read();m=read();
	for(int i=1;i<=n;++i) a[i]=read();
	sq=ceil(sqrt(n));
	for(int i=1;i<=n;++i) bel[i]=(i-1)/sq+1;
	bn=bel[n];
	for(int i=1;i<=bn;++i) lb[i]=(i-1)*sq+1,rb[i]=i*sq;
	rb[bn]=n;
	for(int i=1;i<=m;++i){
		ql[i]=read();qr[i]=read();
		vec[read()].emplace_back(i);
		res[i]=i;
	}
	for(int x=1;x<=bn;++x){
		int tag=0,mn=0x3f3f3f3f;
		for(int i=lb[x];i<=rb[x];++i){
			++cc[arr[i]=-a[i]];
			if(mn>arr[i]) mn=arr[i];
		}
		for(int i=1,j=0;i<=m;++i){
			while(j<=m&&tag+mn<=0){
				if(++j>m) break;
				if(ql[j]<=lb[x]&&rb[x]<=qr[j]) ++tag;
				else{
					int l=max(lb[x],ql[j]),r=min(rb[x],qr[j]);
					for(int t=l;t<=r;++t){
						--cc[arr[t]];
						++cc[++arr[t]];
					}
					if(!cc[mn]) ++mn;
				}
			}
			if(ql[i]<=lb[x]&&rb[x]<=qr[i]){
				--tag;
				if(res[i]<j) res[i]=j-1;
			}
			else{
				int l=max(lb[x],ql[i]),r=min(rb[x],qr[i]);
				for(int t=l;t<=r;++t){
					--cc[arr[t]];
					++cc[--arr[t]];
				}
				if(cc[mn-1]) --mn;
			}
		}
		for(int i=lb[x];i<=rb[x];++i) --cc[arr[i]=-a[i]];
	}
	for(int i=1;i<=m;++i){
		int l=ql[i],r=qr[i];
		ui[l].emplace_back(i);
		ud[r+1].emplace_back(i);
		if(bel[r]-bel[l]<=1){
			qi[l].emplace_back(i);
			qd[r+1].emplace_back(i);
		}
		else{
			qi[l].emplace_back(i);
			qd[rb[bel[l]]+1].emplace_back(i);
			qi[lb[bel[r]]].emplace_back(i);
			qd[r+1].emplace_back(i);
		}
	}
	Block::init();
	for(int ps=1;ps<=n;++ps){
		for(int x:qd[ps]) exi[x]=0;
		for(int i=1;i<=tp;++i) if(exi[s[i]]) ss[++stp]=s[i];
		tp=stp;stp=0;
		for(int i=1;i<=tp;++i) s[i]=ss[i];
		for(int x:qi[ps]) exi[x]=1,s[++tp]=x;
		for(int x:ui[ps]) Block::inc(x);
		for(int x:ud[ps]) Block::dec(x);
		for(int i=1;i<=tp;++i){
			int x=s[i];
			int cur=Block::jump(Block::qry(x)+a[ps]);
			if(cur>res[x]) res[x]=cur-1;
		}
	}
	for(int i=0;i<N;++i){
		int mx=0;
		for(int x:vec[i]){
			int l=x,r=res[x];
			if(mx>=l) l=mx+1;
			if(l<=r){++ans[l];--ans[r+1];}
			if(r>mx) mx=r;
		}
	}
	for(int i=1;i<=m;++i) ans[i]+=ans[i-1];
	for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
	return 0;
}

    但是这个题似乎并不能规约到一些经典根号题，所以说我们可以去思考一下 polylog\text{polylog} 咋做。我们分块做法散块的根号平衡看起来做得很不优美，所以我们考虑只将整块的做法扩展到 polylog\text{polylog}。我们改为用线段树划分整个区间，每个询问在 O(log⁡)O(\log) 个节点处被处理，每个节点处理的询问答案同样具有单调性。我们依旧考虑在每个线段树节点上双指针。

    但是会影响到某个线段树节点的修改看起来很多？考虑我们刚才分块是怎么优化的：注意绝大部分修改都是整块修改，于是直接打标记。线段树同样有这个性质，除开完全包含某个区间的修改，剩下的与该区间有交的修改的量级是 O(nlog⁡n)O(n\log n) 的。考虑线段树每次区间操作只会访问 O(log⁡)O(\log) 个节点所以这个性质是显然的。

    完全包含某个区间的修改的贡献我们可以拿个数据结构（比如树状数组）维护出每次修改的时间。我们发现我们只需要直接从父亲继承这些修改，每次继承之后的变化量之和是 O(nlog⁡n)O(n\log n) 的，所以我们需要按 dfs 序处理这些区间并且动态维护这个树状数组就行了。

    剩下的就和分块差不多，直接对与该区间有交的修改双指针。整块修改的贡献就从树状数组里查一下。求答案时就在树状数组上倍增一下。时间复杂度 O(nlog⁡2n)O(n\log^2 n)。在本题的数据范围下不如单根号快。

    #include <cstdio>
#include <vector>
#include <algorithm>
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=100003;
int n,m;
int ql[N],qr[N],res[N];
vector<int> vec[N];
int ans[N],a[N];
vector<int> qry[N<<2],upd[N<<2];
void hang(int x,int p=1,int l=1,int r=n){
	if(ql[x]<=l&&r<=qr[x]){
		qry[p].emplace_back(x);
		return;
	}
	upd[p].emplace_back(x);
	int mid=(l+r)>>1;
	if(ql[x]<=mid) hang(x,lc,l,mid);
	if(qr[x]>mid) hang(x,rc,mid+1,r);
}
int mn[N<<2],tg[N<<2];
inline void proc(int p,int v){mn[p]+=v;tg[p]+=v;}
inline void pushdown(int p){
	if(tg[p]){
		proc(lc,tg[p]);
		proc(rc,tg[p]);
		tg[p]=0;
	}
}
void build(int p,int l,int r){
	tg[p]=0;
	if(l==r){mn[p]=-a[l];return;}
	int mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	mn[p]=min(mn[lc],mn[rc]);
}
void update(int x,int v,int p,int l,int r){
	if(ql[x]<=l&&r<=qr[x]) return proc(p,v);
	pushdown(p);
	int mid=(l+r)>>1;
	if(ql[x]<=mid) update(x,v,lc,l,mid);
	if(qr[x]>mid) update(x,v,rc,mid+1,r);
	mn[p]=min(mn[lc],mn[rc]);
}
int tr[N];
inline void mdf(int x,int v){for(int i=x;i<=m;i+=(i&-i)) tr[i]+=v;}
inline int ask(int x){
	int res=0;
	for(int i=x;i;i^=(i&-i)) res+=tr[i];
	return res;
}
inline int jump(int v){
	if(!v) return 0;
	int x=0;
	for(int i=16;~i;--i)
		if(x+(1<<i)<=m&&tr[x+(1<<i)]<v) v-=tr[x+=(1<<i)];
	return x+1;
}
void dfs(int p=1,int l=1,int r=n){
	build(p,l,r);
	for(int x:qry[p]) mdf(x,1);
	int len=upd[p].size(),t=0,o=0;
	for(int x:qry[p]){
		int cur=ask(x);
		while(o<len&&upd[p][o]<x) update(upd[p][o++],-1,p,l,r);
		while(t<len&&ask(upd[p][t])-cur+mn[p]<0) update(upd[p][t++],1,p,l,r);
		int pos=jump(cur-mn[p])-1;
		if(t&&pos<upd[p][t-1]) pos=upd[p][t-1]-1;
		if(pos>res[x]) res[x]=pos;
	}
	if(l<r){
		int mid=(l+r)>>1;
		dfs(lc,l,mid);
		dfs(rc,mid+1,r);
	}
	for(int x:qry[p]) mdf(x,-1);
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<=m;++i){
		ql[i]=read();qr[i]=read();
		vec[read()].emplace_back(i);
		res[i]=i;hang(i);
	}
	dfs();
	for(int i=0;i<N;++i){
		int mx=0;
		for(int x:vec[i]){
			int l=x,r=res[x];
			if(mx>=l) l=mx+1;
			if(l<=r){++ans[l];--ans[r+1];}
			if(r>mx) mx=r;
		}
	}
	for(int i=1;i<=m;++i) ans[i]+=ans[i-1];
	for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
	return 0;
}
    • 1

    [集训队互测 2018] 完美的队列

    信息

    ID
    8324
    时间
    5000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 21ms