一些近期的模拟赛，被暴打。
9.19 D
\(m\) 个部落，\(n\) 个洞穴。一开始每个洞穴被 \(a_i\) 占领，或无人。
有两种操作：
-
给出 \(l,r,k\)。区间 \([l,r]\) 更改为 \(k\) 占领。
-
给出 \(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;
}