正睿 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;
}
Comments NOTHING