CF1148H Holy Diver

一、题目

点此看题

二、解法

输入特性要求的做法就应该是移动右端点 \(r\) 然后维护一些东西。

首先考虑怎么维护 \([l,r]\) 的 \(mex\),这个尽量放在简单数据结构上,因为更新它要对应在答案的数据结构上更新。首先观察到 \(mex\) 是关于 \(l\) 不降的,考虑加入某个数字 \(a\),那么影响到的只有 \(mex=a\) 的段 \([p,q]\)

考虑这个段的 \(mex\) 会怎么变化,我们找到最小的权值 \(v>a\) 满足 \(p[v]\leq q\)(其中 \(p[v]\) 表示最后一次出现位置),那么 \((p[v],q]\) 这一段的 \(mex\) 就会等于 \(v\),相当于这里我们寻找了这一段的瓶颈数字。然后我们把 \(a\) 设置成 \(v\),把 \(q\) 设置成 \(p[v]\) 继续循环即可。因为总的段数是 \(O(n)\) 的,而每次修改都会增加一段,均摊的修改次数是 \(O(n)\) 的。

具体实现中可以用线段树二分维护 \(p\) 数组来支持查询。

高维统计问题可以考虑贡献法、差分法,考虑一个修改 \((i,l,r,x)\),也就是在时刻 \(i\) 把区间 \([l,r]\) 的权值永久修改成 \(x\)(这里需要差分,我们在删除的时候添加一个负修改即可),然后如果在时刻 \(j\) 来查询(时刻的意思就是右端点),那么这个修改的贡献是 \(j-i+1\),那么我们在线段树维护系数 \(1\) 和 \(i\) 就可以查询了。

对于每一种权值我们都需要开一棵线段树,所以我们动态开点,共用一个内存池即可。因为可能查询到以前的时刻,所以需要使用标记永久化的主席树,时间复杂度 \(O(n\log n)\)

三、总结

高位统计问题(比如统计一个区间的子区间),可以考虑维护历史和;也可以考虑计算每一个修改的贡献,这时候利用差分把它变成永久修改便于计算。

对于如何维护一个东西要有总体观念,比如本题的维护 \(mex\),因为要把修改打在线段树上不可能用一些复杂结构,而只能暴力修改。所以你需要想清楚维护应该是立刻的,还是延时的

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int M = 200005;
const int N = 60*M;
#define int long long
#define pii pair<int,int>
#define mp make_pair
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,cnt,ls[N],rs[N],s1[N],s2[N],t1[N],t2[N];
struct node
{
	int w,l,r;
	bool operator < (const node &b) const
	{
		return w==b.w?r<b.r:w<b.w;
	}
};set<node> s;
namespace T1
{
	int mi[4*M];
	void ins(int i,int l,int r,int id,int x)
	{
		if(l==r) {mi[i]=x;return ;}
		int mid=(l+r)>>1;
		if(mid>=id) ins(i<<1,l,mid,id,x);
		else ins(i<<1|1,mid+1,r,id,x);
		mi[i]=min(mi[i<<1],mi[i<<1|1]);
	}
	pii ask(int i,int l,int r,int id,int x)
	{
		if(mi[i]>x) return mp(0,0);
		if(l==r) return mp(l,mi[i]);
		int mid=(l+r)>>1;
		if(mid>=id)
		{
			pii t=ask(i<<1,l,mid,id,x);
			return !t.first?ask(i<<1|1,mid+1,r,id,x):t;
		}
		return ask(i<<1|1,mid+1,r,id,x);
	}
}
struct T2
{
	vector<int> pos,rt;int w1,w2;
	void add(int &x,int y,int l,int r,int L,int R)
	{
		if(l>R || L>r) return ;
		x=++cnt;
		ls[x]=ls[y];rs[x]=rs[y];t2[x]=t2[y];
		s1[x]=s1[y];s2[x]=s2[y];t1[x]=t1[y];
		if(L<=l && r<=R)
		{
			s1[x]+=w1*(r-l+1);t1[x]+=w1;
			s2[x]+=w2*(r-l+1);t2[x]+=w2;
			return ;
		}
		int mid=(l+r)>>1;
		add(ls[x],ls[y],l,mid,L,R);
		add(rs[x],rs[y],mid+1,r,L,R);
		s1[x]=s1[ls[x]]+s1[rs[x]]+(r-l+1)*t1[x];
		s2[x]=s2[ls[x]]+s2[rs[x]]+(r-l+1)*t2[x];
	}
	pii ask(int x,int l,int r,int L,int R)
	{
		if(L>r || l>R || !x) return mp(0,0);
		if(L<=l && r<=R) return mp(s1[x],s2[x]);
		int mid=(l+r)>>1,len=min(r,R)-max(L,l)+1;
		pii v1=ask(ls[x],l,mid,L,R),
		v2=ask(rs[x],mid+1,r,L,R);
		return mp(v1.first+v2.first+t1[x]*len,
		v1.second+v2.second+t2[x]*len);
	}
	void ins(int i,int l,int r,int a,int b)
	{
		rt.push_back(0);pos.push_back(i);
		w1=a;w2=b;int p=rt.size()-1;
		add(rt[p],p?rt[p-1]:0,1,n,l,r);
	}
	int qry(int l,int r)
	{
		int q=upper_bound(pos.begin(),pos.end(),r)-
		pos.begin()-1;if(q<0) return 0;
		pii ans=ask(rt[q],1,n,l,r);
		return ans.first*(r+1)-ans.second;
	}
}h[M];
int zxy(int a,int l,int r,int k,int i)
{
	int u=a?0:1;T1::ins(1,0,n,a,i);
	set<node>::iterator it=s.lower_bound(node{a,0,0});
	if(it!=s.end() && it->w==a)
	{
		int p=it->l,q=it->r;s.erase(it);
		//delete the everlasting tag
		h[a].ins(i,p,q,-1,-i);
		while(p<=q)//work for the new mex
		{
			pii nx=T1::ask(1,0,n,a+1,q);
			if(nx.second<p)//all mex=a
			{
				s.insert(node{nx.first,p,q});
				h[nx.first].ins(i,p,q,1,i);
				a=nx.first;break;
			}
			if(nx.second<q)//(nx,q] mex=a
			{
				s.insert(node{nx.first,nx.second+1,q});
				h[nx.first].ins(i,nx.second+1,q,1,i);
			}
			a=nx.first;q=nx.second;
		}
		//now we merge the same segment
		it=s.lower_bound(node{a,0,0});
		if(it!=s.end() && it->w==a)
		{
			node tmp=*it;it++;
			if(it!=s.end() && it->w==a)
			{
				s.erase(s.find(tmp));
				tmp.r=it->r;
				s.erase(it);
				s.insert(tmp);
			}
		}
	}
	it=s.lower_bound(node{u,0,0});
	if(it!=s.end() && it->w==u)
	{
		node tmp=*it;tmp.r++;
		s.erase(it);s.insert(tmp);
	}
	else s.insert(node{u,i,i});
	h[u].ins(i,i,i,1,i);
	return h[k].qry(l,r);
}
signed main()
{
	n=read();int ans=0;
	for(int i=1;i<=n;i++)
	{
		int a=read(),l=read(),r=read(),k=read();
		a=(a+ans)%(n+1);k=(k+ans)%(n+1);
		l=(l+ans)%i+1;r=(r+ans)%i+1;
		if(l>r) swap(l,r);
		printf("%lld\n",ans=zxy(a,l,r,k,i));
	}
}
上一篇:搞懂钩子方法和模板方法,看完这篇就够了


下一篇:#01-Trie,Cayley定理#51nod 1601 完全图的最小生成树计数