正睿 CSP 七连测 Day2
Oblivion
设 $dp_i$ 表示仅考虑 $1$ 到 $i$ 且 $i$ 邪恶的方案数。考虑枚举一个左端点 $j$，表示 $j$ 到 $i$ 中的人都是善良的，那方案合法当且仅当 $j$ 到 $\lfloor \frac{i+j}{2}\rfloor $ 中所有有指向的都为 L，$\lfloor \frac{i+j}{2}\rfloor +1$ 到 $i $ 中所有有指向的都为 R。同样需要考虑 $i$ 作为第一个邪恶的人的方案数，只需满足 $i$ 以前的所有有指向的人都指向 R 即可。$dp_i$ 对答案产生贡献当且仅当 $i+1$ 到 $n$ 所有有指向的人都指向 L 。复杂度 $O(n^2)$。
考虑进行一些优化，对于这个 $j$ 的统计，我们转换一下思维，设 $l_i$ 表示从 $1$ 到 $n$ 中下标最大的 L，$r_i$ 表示 $i$ 到 $n$ 中下标最小的 R。对于一个符合条件的 $j$，一定有：
$$
\begin{cases}
2l_{i-1}\le i+j \\
2r_{j+1}>i+j
\end{cases}
$$
稍微移项一下就可以得到一个很好用 BIT 维护的差分关系，代码如下：
C++
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
const int mod=998244353;
int n,ans;
int suml[N],sumr[N],l[N],r[N],dp[N];
char c[N];
vector<int> g[N];
struct BIT{
int tr[N];
void add(int x,int k){
for(;x<=n;x+=x&-x) (tr[x]+=k)%=mod;
}
int get(int x){
if(x<=0) return 0;
int res=0;
for(;x>0;x-=x&-x) (res+=tr[x])%=mod;
return res;
}
}bit;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[i];
l[i]=(c[i]=='L'?i:l[i-1]);
suml[i]=suml[i-1]+(c[i]=='L');
sumr[i]=sumr[i-1]+(c[i]=='R');
}
r[n+1]=n+1;
for(int i=n;i>=1;i--) r[i]=(c[i]=='R'?i:r[i+1]);
for(int i=1;i<=n;i++){
for(int x:g[i]) bit.add(x,-dp[x]);
if(!suml[i-1]) dp[i]=1;
// for(int j=1;j<i;j++){
// int mid=(i+j)>>1;
// if(!(sumr[mid]-sumr[j])&&!(suml[i-1]-suml[mid])) (dp[i]+=dp[j])%=mod;
// }
(dp[i]+=bit.get(i)-bit.get(2*l[i-1]-i-1))%=mod;
(dp[i]+=mod)%=mod;
if(suml[i]==suml[i-1]&&sumr[i]==sumr[i-1]) (dp[i]<<=1)%=mod;
bit.add(i,dp[i]);
if(2*r[i+1]-i<=n) g[2*r[i+1]-i].push_back(i);
if(!(sumr[n]-sumr[i])) (ans+=dp[i])%=mod;
}
cout<<(ans%mod+mod)%mod;
return 0;
}正睿 NOIP 十连测 Day1
序列
按值从大到小进行枚举，设当前所有数中位置最左和最右分别为 $l$，$r$，并且枚举了 $x$ 个数，那有答案为 $r-l+1-x+2$
树
考虑树上主席树，这个主席树存的是颜色编号区间内各个颜色数量的信息，这样的话答案就可以二分去找了。但是这个信息直接存储的话应该是一个数组，考虑给每个颜色赋一个随机数权值，比较权值即可。
代码：
C++
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls(p) (tr[(p)].l)
#define rs(p) (tr[(p)].r)
const int N=3e5+5;
int n,q,idx;
int rt[N],col[N],dep[N],val[N],fa[N][20];
vector<int> g[N];
struct tree{
int l,r,sum;
}tr[N*60];
mt19937_64 rnd(rand());
void read(int &x){
int f=1;
x=0;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
x*=f;
}
int insert(int f,int l,int r,int x){
int p=++idx;
tr[p]=tr[f],tr[p].sum+=val[x];
if(l==r) return p;
int mid=(l+r)>>1;
if(x<=mid) ls(p)=insert(ls(f),l,mid,x);
else rs(p)=insert(rs(f),mid+1,r,x);
return p;
}
void dfs(int u,int f){
fa[u][0]=f,dep[u]=dep[f]+1;
rt[u]=insert(rt[f],1,n,col[u]);
for(int i=1;i<20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
for(int v:g[u]){
if(v==f) continue;
dfs(v,u);
}
}
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
for(int i=19;i>=0;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
if(u==v) return u;
for(int i=19;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
int solve(int u1,int v1,int l1,int f1,int u2,int v2,int l2,int f2,int l,int r){
if(l==r) return l-1;
int h1=tr[ls(u1)].sum+tr[ls(v1)].sum-tr[ls(l1)].sum-tr[ls(f1)].sum,
h2=tr[ls(u2)].sum+tr[ls(v2)].sum-tr[ls(l2)].sum-tr[ls(f2)].sum;
int mid=(l+r)>>1;
if(h1!=h2) return solve(ls(u1),ls(v1),ls(l1),ls(f1),ls(u2),ls(v2),ls(l2),ls(f2),l,mid);
else return solve(rs(u1),rs(v1),rs(l1),rs(f1),rs(u2),rs(v2),rs(l2),rs(f2),mid+1,r);
}
signed main(){
read(n);
for(int i=1,u,v;i<n;i++){
read(u),read(v);
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++) read(col[i]),val[i]=rnd();
dfs(1,0);
read(q);
while(q--){
int u1,v1,u2,v2;
read(u1),read(v1),read(u2),read(v2);
int l1=lca(u1,v1),l2=lca(u2,v2),f1=fa[l1][0],f2=fa[l2][0];
int h1=tr[rt[u1]].sum+tr[rt[v1]].sum-tr[rt[l1]].sum-tr[rt[f1]].sum,
h2=tr[rt[u2]].sum+tr[rt[v2]].sum-tr[rt[l2]].sum-tr[rt[f2]].sum;
if(h1==h2){
printf("%d\n",n);
continue;
}
printf("%d\n",solve(rt[u1],rt[v1],rt[l1],rt[f1],rt[u2],rt[v2],rt[l2],rt[f2],1,n));
}
return 0;
}六元组
设三架飞机按停放机场排序后为 $x_a<x_b<x_c$，则 $a,b$ 向右飞，$c$ 向左飞。方案合法当且仅当：
$$
\begin{cases}
x_b\in[l_a,r_a]\\
x_c\in[l_b,r_b]\\
x_a\in[l_c,r_c]
\end{cases}
$$
考虑枚举 $b$，先算所有 $b\to c$ 的贡献，再算 $a\to b$ 的传递，最后对每个 $c$ 查询 $x_a\in[l_c,r_c]$ 的总贡献。
具体地，把飞机按 $x$ 排序后离散化区间，分块预处理 $f[k][i][j]$ 表示从块 $i$ 出发经过 $k$ 次向右传递后对位置 $j$ 的贡献。$k=0$ 时块内每个点初始为 $1$，$k=1$ 时每个 $b$ 对它区间内的点贡献 $+1$，$k=2$ 时每个 $a$ 对它区间内的点贡献 $+1$。
扫描线枚举 $c$，用差分数组维护当前所有 $a$ 的贡献，整块直接加 $f[2][j][i]$，散块暴力查询差分即可。复杂度 $O(m\sqrt m)$。
代码：
C++
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,B=450;
int n,m,bl;
long long ans;
int t[N],l[N],r[N],val[N],tag[N],f[3][N/B+5][N];
vector<pair<int,int>> v[N];
struct node{
int x,l,r;
}a[N];
bool cmp(node a,node b){
return a.x<b.x;
}
void add(int x,int v){
int b=(x-1)/B+1;
for(int i=1;i<b;i++) tag[i]+=v;
for(int i=(b-1)*B+1;i<=x;i++) val[i]+=v;
}
int query(int x){
return tag[(x-1)/B+1]+val[x];
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
bl=(m+B-1)/B;
for(int i=1;i<=m;i++) cin>>a[i].x>>a[i].l>>a[i].r,a[i].r++;
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++) t[i]=a[i].x;
for(int i=1;i<=m;i++){
l[i]=lower_bound(t+1,t+m+1,a[i].l)-t;
r[i]=lower_bound(t+1,t+m+1,a[i].r)-t;
v[l[i]].push_back({i,1});
v[r[i]].push_back({i,-1});
}
for(int i=1;i<=bl;i++){
for(int j=(i-1)*B+1;j<=min(i*B,m);j++) f[0][i][j]=1;
for(int k=1;k<=2;k++){
for(int j=1;j<=m;j++){
f[k][i][l[j]]+=f[k-1][i][j];
f[k][i][r[j]]-=f[k-1][i][j];
}
for(int j=1;j<=m;j++) f[k][i][j+1]+=f[k][i][j];
}
}
for(int i=1;i<=m;i++){
for(auto p:v[i]) add(p.first,p.second);
int L=(l[i]-1)/B+1,R=(r[i]-1)/B+1;
for(int j=L;j<R;j++) ans+=f[2][j][i];
for(int j=(L-1)*B+1;j<l[i];j++) ans-=query(l[j])-query(r[j]);
for(int j=(R-1)*B+1;j<r[i];j++) ans+=query(l[j])-query(r[j]);
}
cout<<ans<<"\n";
return 0;
}
Comments NOTHING