一些近期的模拟赛，被暴打。

9.19 D

\(m\) 个部落，\(n\) 个洞穴。一开始每个洞穴被 \(a_i\) 占领，或无人。

有两种操作：

1. 给出 \(l,r,k\)。区间 \([l,r]\) 更改为 \(k\) 占领。

2. 给出 \(l,r,k\)。区间 \([l,r]\) 的每个洞穴出现价值为 \(k\) 的宝物，由占领该洞穴的部落获得，若无部落占领，则由下一个占领的部落获得。

求最终各个部落获得的宝物价值总和。

想了一会在线，发现不是很可做。反着做也想了好一会，鉴定为对数据结构的使用不够熟练。

想到反着做就基本结束了其实，原本的 1 操作就是 \(ans_k\) 加上区间和，然后区间归零。

2 操作就是一个简单的区间加。

懒得打了于是 Copy 的线段树 2，区间归零就是区间乘 \(0\)。

#include<bits/stdc++.h>
#pragma GCC optimize(2,3,"Ofast","inline")
#define int long long
using namespace std;
const int N=5e5+10;
int n,m,q;
int c[N],ans[N];
struct node
{
	int op,l,r,x;
}a[N];
struct ccf
{
	int l,r,num,la1,la2;
}f[N<<2];
void build(int k,int l,int r)
{
	f[k].l=l,f[k].r=r,f[k].la1=1,f[k].la2=0;
	if(l==r)return ;
	int mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
}
void pushdown(int k)
{
	if(f[k].la1!=1||f[k].la2)
	{
		int l=k*2,r=k*2+1;
		f[l].num*=f[k].la1;
		f[l].num+=(f[l].r-f[l].l+1)*f[k].la2;
		f[r].num*=f[k].la1;
		f[r].num+=(f[r].r-f[r].l+1)*f[k].la2;
		f[l].la1*=f[k].la1;
		f[l].la2=f[l].la2*f[k].la1+f[k].la2;
		f[r].la1*=f[k].la1;
		f[r].la2=f[r].la2*f[k].la1+f[k].la2;
		f[k].la1=1,f[k].la2=0;
	}
}
void change(int k,int l,int r,int x,int y,int v,int op)
{
	if(l>y||r<x)return ;
	if(x<=l&&r<=y)
	{
		if(op==1)f[k].num*=v,f[k].la1*=v,f[k].la2*=v;
		else f[k].num+=(r-l+1)*v,f[k].la2+=v;
		return ;
	}
	pushdown(k);
	int mid=(l+r)/2;
	change(k*2,l,mid,x,y,v,op);
	change(k*2+1,mid+1,r,x,y,v,op);
	f[k].num=f[k*2].num+f[k*2+1].num;
}
int ask(int k,int l,int r,int x,int y)
{
	if(l>y||r<x)return 0;
	if(x<=l&&r<=y)return f[k].num;
	pushdown(k);
	int mid=(l+r)/2;
	return ask(k*2,l,mid,x,y)+ask(k*2+1,mid+1,r,x,y);
}
signed main()
{
	cin>>n>>m>>q;
	build(1,1,n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&c[i]);
	for(int i=1;i<=q;i++)
		scanf("%lld%lld%lld%lld",&a[i].op,&a[i].l,&a[i].r,&a[i].x);
	build(1,1,n);
	for(int i=q;i>=1;i--)
	{
		if(a[i].op==1)
		{
			ans[a[i].x]+=ask(1,1,n,a[i].l,a[i].r);
			change(1,1,n,a[i].l,a[i].r,0,1);
		}
		else change(1,1,n,a[i].l,a[i].r,a[i].x,2);
	}
	for(int i=1;i<=n;i++)
		if(c[i])ans[c[i]]+=ask(1,1,n,i,i);
	for(int i=1;i<=m;i++)
		printf("%lld\n",ans[i]);
	return 0;
}

9.24 D

给出一个 \(n\) 个点，\(m\) 条边的有向图，求有多少个点集 \(S\) 满足，\(\forall i\in S\)，若存在边 \((i,j)\)，则 \(j\in S\)。同时点集 \(S\) 是连续的，即点的编号是连续的。

一眼顶针 \(O(n^2)\) 做法，枚举左右端点：

#include<bits/stdc++.h>
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
using namespace std;
const int N=3e5+10;
int n,m,ans;
int x[N],y[N];
vector<int>v[N];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
	}
	memset(x,127,sizeof(x));
	for(int i=1;i<=n;i++)
		for(int k:v[i])
			x[i]=min(k,x[i]),y[i]=max(k,y[i]);
	for(int i=1;i<=n;i++)
	{
		int mi=1e9,ma=0;
		for(int j=i;j<=n;j++)
		{
			mi=min(mi,x[j]),ma=max(ma,y[j]);
			if(mi<i)break;
			if(ma<=j)ans++;
		}
	}
	cout<<ans;
	return 0;
}

然后就不会优化了，鉴定为不会用数据结构。

琢磨了一下午，但还是不会。场上切这题的人还不少。

问了大神，表示这是线段树应用模板。

对于每个 \(i\)，它为左端点的贡献区间只有 \([i,r_i]\)，这个 \(r_i\) 是可以二分在 \(\mathcal O(n)\) 内求出来的，那么可以在枚举右端点到 \(i\) 时丢到线段树上，然后在 \(r_i\) 时将它再拿出来。

同样的，它为右端点的贡献区间为 \([l_i,i]\)，\(l_i\) 可以二分，然后在线段树求区间 \([l_i,i]\) 的和即可。

用 st 表预处理可以做到 \(\mathcal O(n\log n)\)。

线段树还是要多练啊！！！！！

#include<bits/stdc++.h>
#define int long long
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
using namespace std;
const int N=3e5+10,mod=1e9+7;
int n,m,ans;
int mi[N],ma[N],st[N][25],ts[N][25],f[N<<2];
vector<int>v[N];
int check(int l,int r)
{
	if(l>r)return 1e9;
	int k=log2(r-l+1);
	return min(st[l][k],st[r-(1<<k)+1][k]);
}
int chec(int l,int r)
{
	int k=log2(r-l+1);
	return max(ts[l][k],ts[r-(1<<k)+1][k]);
}
int find(int k)
{
	int l=k-1,r=n+1;
	while(l+1<r)
	{
		int mid=(l+r)/2;
		if(check(k,mid)>=k)l=mid;
		else r=mid;
	}
	return l;
}
int fin(int k)
{
	int l=0,r=k+1;
	while(l+1<r)
	{
		int mid=(l+r)/2;
		if(chec(mid,k)<=k)r=mid;
		else l=mid;
	}
	return r;
}
void add(int k,int l,int r,int x,int y)
{
	if(l==r)return f[k]+=y,void();
	int mid=(l+r)/2;
	if(x<=mid)add(k*2,l,mid,x,y);
	else add(k*2+1,mid+1,r,x,y);
	f[k]=f[k*2]+f[k*2+1];
}
int ask(int k,int l,int r,int x,int y)
{
	if(l>y||r<x)return 0;
	if(x<=l&&r<=y)return f[k];
	int mid=(l+r)/2;
	return ask(k*2,l,mid,x,y)+ask(k*2+1,mid+1,r,x,y);
}
signed main()
{
	memset(mi,127,sizeof(mi));
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		mi[x]=min(mi[x],y);
		ma[x]=max(ma[x],y);
	}
	for(int i=1;i<=n;i++)
	{
		if(!ma[i])ma[i]=i;
		st[i][0]=mi[i];
		ts[i][0]=ma[i];
	}
	for(int j=1;j<=20;j++)
		for(int i=1;i+(1<<j-1)<=n;i++)
			st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]),
			ts[i][j]=max(ts[i][j-1],ts[i+(1<<j-1)][j-1]);
	for(int i=1;i<=n;i++)
		if(mi[i]>=i)v[find(i)+1].push_back(i);
	for(int i=1;i<=n;i++)
	{
		if(mi[i]>=i)add(1,1,n,i,1);
		for(int j:v[i])
			add(1,1,n,j,-1);
		ans+=ask(1,1,n,fin(i),i);
	}
	cout<<ans%mod;
	return 0;
}