2023.5 做题笔记
【Ptz2022 Summer】Ternary Search
两种目标序列是类似的，这里只考虑第一种（单谷），单峰的话把所有数 \(x\) 变成 \(n-x+1\) 再算一遍就行。
一个数要么放到左边，要么放到右边。放到左边的代价是左边比它大的数的个数，记作 \(w_1\)，放到右边的代价是右边比它大的数的个数，记作 \(w_2\)，其产生的贡献是 \(\min\{w_1,w_2\}\)，将所有数的贡献加起来就是答案。
然后考虑对每个前缀算答案，此时每个数 \(w_1\) 是不变的，在后面加入一个数，会对前面所有小于它的数的 \(w_2\) 产生 \(1\) 的贡献。也就是说，一个数在一个前缀中将 \(w_2\) 计入贡献，在一个后缀中将 \(w_1\) 计入贡献。可以线段树二分找到这个分界点，维护计入贡献的 \(w_2\) 的总增量是容易的，复杂度 \(O(n \log n)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,Tp;
int a[500005],pos[500005],w1[500005];
vector <int> todel[500005];
struct BIT
{
int t[500005];
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int d)
{
for(int i=x;i<=n;i+=lowbit(i)) t[i]+=d;
}
int query(int x)
{
int res=0;
for(int i=x;i>=1;i-=lowbit(i)) res+=t[i];
return res;
}
}bt;
int t[2000005];
void update(int id,int l,int r,int x,int d)
{
t[id]+=d;
if(l==r) return;
int mid=(l+r)>>1;
if(x<=mid) update(id<<1,l,mid,x,d);
else update(id<<1|1,mid+1,r,x,d);
}
int get_kth(int id,int l,int r,int k)
{
if(l==r) return l;
int mid=(l+r)>>1;
if(k<=t[id<<1]) return get_kth(id<<1,l,mid,k);
else return get_kth(id<<1|1,mid+1,r,k-t[id<<1]);
}
int get_rk(int id,int l,int r,int x)
{
if(!x) return 0;
if(l==r) return t[id];
int mid=(l+r)>>1;
if(x<=mid) return get_rk(id<<1,l,mid,x);
else return t[id<<1]+get_rk(id<<1|1,mid+1,r,x);
}
ll Ans[500005];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
vector <int> vec;
for(int i=1;i<=n;i++) vec.pb(a[i]);
sort(vec.begin(),vec.end());
for(int i=1;i<=n;i++) a[i]=lower_bound(vec.begin(),vec.end(),a[i])-vec.begin()+1,pos[a[i]]=i;
for(int i=1;i<=n;i++)
{
w1[i]=i-1-bt.query(a[i]);
bt.update(a[i],1);
}
memset(bt.t,0,sizeof(bt.t));
for(int i=n;i>=1;i--)
{
int x=pos[i];
update(1,1,n,x,1);
int r=get_rk(1,1,n,x);
if(r+w1[x]>t[1]) continue;
int tmp=get_kth(1,1,n,r+w1[x]);
todel[tmp].pb(i);
}
ll ans=0;
for(int i=1;i<=n;i++)
{
ans+=1LL*bt.query(a[i]);
bt.update(a[i],1);
for(int j=0;j<todel[i].size();j++) bt.update(todel[i][j],-1);
Ans[i]=ans;
}
for(int i=1;i<=n;i++) a[i]=n-a[i]+1,pos[a[i]]=i,todel[i].clear();
memset(bt.t,0,sizeof(bt.t));
memset(t,0,sizeof(t));
for(int i=1;i<=n;i++)
{
w1[i]=i-1-bt.query(a[i]);
bt.update(a[i],1);
}
memset(bt.t,0,sizeof(bt.t));
for(int i=n;i>=1;i--)
{
int x=pos[i];
update(1,1,n,x,1);
int r=get_rk(1,1,n,x);
if(r+w1[x]>t[1]) continue;
int tmp=get_kth(1,1,n,r+w1[x]);
todel[tmp].pb(i);
}
ans=0;
for(int i=1;i<=n;i++)
{
ans+=1LL*bt.query(a[i]);
bt.update(a[i],1);
for(int j=0;j<todel[i].size();j++) bt.update(todel[i][j],-1);
cout<<min(Ans[i],ans)<<"\n";
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
【FJOI2022/CF1510H】区间子集问题
这是篇正经题解（
先建出一个森林的结构，一个区间的父亲是包含它的最短区间。
一个点的子区间的选择，显然的，要么下放到某一个儿子里面选择，要么完全覆盖一段空隙，要么覆盖最左边的儿子的左边，要么覆盖最右边的儿子的右边。
令 \(dp(u,k,0/1,0/1)\) 表示，考虑 \(u\) 的子树，从上面下放下来了 \(k\) 个区间，目前是否有一个可以和左边合并的区间，是否有一个可以和右边合并的区间，转移可能有点麻烦，要特判第一个儿子和最后一个儿子。如果要卡空间，在合并儿子的时候可以使用滚动数组。复杂度 \(O(n^2)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,L[5005],R[5005];
vector <int> g[5005],rts;
int dp[5005][5005][2][2],f[5005][2][2];
int sz[5005];
bool cmp(int x,int y)
{
return L[x]<L[y];
}
void dfs(int u)
{
sz[u]=1;
sort(g[u].begin(),g[u].end(),cmp);
dp[u][0][0][0]=dp[u][0][1][1]=0;
dp[u][0][0][1]=-L[u],dp[u][0][1][0]=L[u];
for(int i=0;i<g[u].size();i++) dfs(g[u][i]);
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
memset(f,-0x3f,sizeof(f));
for(int j=0;j<=sz[u];j++) for(int k=0;k<=sz[v];k++) for(int p=0;p<2;p++) for(int s=0;s<2;s++) for(int m=0;m<2;m++)
f[j+k+m][p][s]=max(f[j+k+m][p][s],dp[u][j][p][m]+dp[v][k][m][s]);
sz[u]+=sz[v];
for(int j=0;j<=sz[u];j++) for(int p=0;p<2;p++) for(int s=0;s<2;s++) dp[u][j][p][s]=max((i==0?dp[v][j][p][s]:-inf),f[j][p][s]);
}
memset(f,-0x3f,sizeof(f));
for(int i=0;i<=sz[u];i++) for(int p=0;p<2;p++) for(int s=0;s<2;s++) for(int m=0;m<2;m++)
{
int w=0;
if(m==1&&s==0) w=R[u];
if(m==0&&s==1) w=-R[u];
f[i+m][p][s]=max(f[i+m][p][s],dp[u][i][p][m]+w);
}
for(int i=0;i<=sz[u];i++) for(int p=0;p<2;p++) for(int s=0;s<2;s++) dp[u][i][p][s]=max(dp[u][i+1][p][s],f[i+1][p][s]);
/* cout<<u<<endl;
for(int p=0;p<2;p++) for(int s=0;s<2;s++)
{
for(int i=0;i<=sz[u];i++) cout<<dp[u][i][p][s]<<" ";
puts("");
}
system("pause");*/
}
void solve()
{
memset(dp,-0x3f,sizeof(dp));
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&L[i],&R[i]);
for(int i=1;i<=n;i++)
{
int fa=-1;
for(int j=1;j<=n;j++) if(j!=i&&L[j]<L[i]&&R[i]<R[j])
if(fa==-1||L[j]>L[fa]) fa=j;
if(fa!=-1) g[fa].pb(i);
else rts.pb(i);
// cout<<fa<<" "<<i<<endl;
}
int ans=0;
for(int i=0;i<rts.size();i++) dfs(rts[i]),ans+=dp[rts[i]][0][0][0];//,cout<<"... "<<rts[i]<<" "<<ans<<endl;
printf("%d\n",ans);
}
signed main()
{
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
【集训队作业2018】count
容易发现两个序列同构，当且仅当它们的笛卡尔树同构。
先特判 \(m \gt n\)，一个笛卡尔树能被构造出来当且仅当它不存在一条长度 \(\gt m\) 的左链（其实右链是等价的，这里说左链方便一点）。
然后逆用普通树转二叉树的”左儿子右兄弟“表示法，将二叉树的左儿子变为新树的儿子，右儿子变为它的兄弟（也就是拉平右链的一个过程），这样一个二叉树就能和一个普通树形成一一映射，最长左链就是普通树的深度。
考虑括号序列，即求长度为 \(2n\)，前缀和（左括号看成 \(+1\)，右括号看成 \(-1\)） \(\le m\) 的方案数。一个常用的 trick：令 \(+1\) 表示往右走，\(-1\) 表示往上走，要求的是在两条直线之间，从 \((0,0)\) 走到 \((n,n)\) 的方案数。计算方法为容斥+折线法，枚举走出去的位置，把上面的翻折下来，就可以轻松计算。
附一个详细的解释： link。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int fpow(int x,int b){
if(x==0) return 0;
if(b==0) return 1;
int res=1;
while(b>0){
if(b&1) res=1LL*res*x%mod;
x=1LL*x*x%mod;
b>>=1;
}
return res;
}
int fac[300005],ifac[300005];
int C(int x,int y)
{
if(y>x) return 0;
if(x==y||y==0) return 1;
return 1LL*fac[x]*ifac[x-y]%mod*ifac[y]%mod;
}
void init(int x)
{
fac[0]=fac[1]=1;
for(int i=2;i<=x;i++) fac[i]=1LL*fac[i-1]*i%mod;
ifac[x]=fpow(fac[x],mod-2);
for(int i=x-1;i>=0;i--) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
void solve()
{
init(200000);
int ans=0;
int n,m;
cin>>n>>m;
if(m>n)
{
puts("0");
return;
}
ans=C(2*n,n);
for(int i=1;n-(i-1)*m-2*i+1>=0;i++) ans=(ans-C(2*n,n-(i-1)*m-2*i+1)+mod)%mod;
for(int i=1;n+i*m+2*i<=2*n;i++) ans=(ans+C(2*n,n+i*m+2*i))%mod;
for(int i=1;n+i*m+2*i-1<=2*n;i++) ans=(ans-C(2*n,n+i*m+2*i-1)+mod)%mod;
for(int i=1;n-i*m-2*i>=0;i++) ans=(ans+C(2*n,n-i*m-2*i))%mod;
cout<<ans;
}
signed main()
{
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
【ECNU Coder 2018】棋盘染色
\(m\) 很小，考虑对 \(m\) 这一维状压 + 轮廓线 dp，你需要记录轮廓线上的：每个位置是黑色和白色，还有同色之间的联通情况，暴力搜显然状态数超标，一个显然的剪枝是，钦定相邻两个同色位置在同一个连通块（注意特殊处理转折点），这个加上搜出来也就只有 \(3 \times 10^4\) 左右。还有一个剪枝就是如果存在 \((a,b,c,d)\) 满足 \(a \lt b \lt c \lt d\)，\(a,c\) 同色不同块，\(b,d\) 同色不同块，也可以剪枝，code 中这个剪枝没加，加上去的话状态会大大缩小。
然后是 dp 的转移，可以对于每一种轮廓线，预处理出在 \(m\) 个位置放哪种颜色会转移到哪种轮廓线，可以建出一个自动机，直接在这个自动机上进行 dp 就行，复杂度视搜出来的状态数而定。
Code
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
int mod;
const int inf=0x3f3f3f3f;
int col[8],cnt;
int m;
int ma[80000005];
vector <int> val[30705];
int gethsh(vector <int> vec)
{
for(int i=0;i<vec.size();i++) vec[i]+=100;
for(int i=0,x0=0,x1=1;i<vec.size();i++) if(vec[i]>=100)
{
int now=(vec[i]%2==0?x0:x1);
if(vec[i]%2==0) x0+=2;
else x1+=2;
int tmp=vec[i];
for(int j=i;j<vec.size();j++) if(vec[j]==tmp) vec[j]=now;
}
int hv=0;
for(int i=0;i<m;i++) hv=hv*10+vec[i];
if(!ma[hv]) return -1;
return ma[hv];
}
void chk()
{
/* for(int i=0;i<m;i++) for(int j=i+1;j<m;j++) if(col[i]%2==col[j]%2&&col[i]!=col[j])
{
for(int x=i+1;x<j;x++) for(int y=j+1;y<m;y++) if(col[x]%2!=col[i]%2&&col[x]%2==col[y]%2&&col[x]!=col[y]) return;
}*/
cnt++;
int hv=0;
for(int i=0;i<m;i++) hv=hv*10+col[i];
ma[hv]=cnt;
for(int i=0;i<m;i++) val[cnt].pb(col[i]);
return;
}
void dfs(int u,int op)
{
if(u==m)
{
chk();
return;
}
if(u==0)
{
col[u]=0;
dfs(u+1,op);
col[u]=1;
dfs(u+1,op);
return;
}
int maxx=-1;
for(int i=0;i<u;i++) if(col[i]%2!=col[u-1]%2) maxx=max(maxx,col[i]);
if(maxx==-1) maxx=(col[u-1]%2==0?1:0);
else maxx+=2;
while(maxx>=0) col[u]=maxx,dfs(u+1,op),maxx-=2;
maxx=-1;
for(int i=0;i<u;i++) if(col[i]%2==col[u-1]%2) maxx=max(maxx,col[i]);
maxx+=2;
while(maxx>=0)
{
int op2=op;
if(maxx!=col[u-1]) op2++;
if(op2<=1) col[u]=maxx,dfs(u+1,op2);
maxx-=2;
}
}
int n;
int dp[2][30705];
int g[2][8];
void merge(int x,int y)
{
for(int i=0;i<2;i++) for(int j=0;j<m;j++) if(g[i][j]==x) g[i][j]=y;
}
int nxt[30705][8][2];
void solve()
{
cin>>n>>m>>mod;
dfs(0,0);
// cout<<cnt<<endl;
for(int t=1;t<=cnt;t++)
{
for(int x=0;x<m;x++) for(int d=0;d<2;d++)
{
memset(g,-1,sizeof(g));
for(int i=0;i<m;i++) g[0][i]=val[t][i];
for(int i=0;i<x;i++) swap(g[0][i],g[1][i]);
g[1][x]=d+10;
if(x&&g[1][x-1]%2==d) merge(g[1][x-1],g[1][x]);
if(g[0][x]%2==d) merge(g[0][x],g[1][x]);
int cnt1=0,cnt2=0;
for(int i=0;i<2;i++) for(int j=0;j<m;j++) if(g[i][j]!=-1)
{
if(g[i][j]==g[0][x]) cnt1++;
if(g[i][j]%2==g[0][x]%2) cnt2++;
}
if(cnt1==1)
{
nxt[t][x][d]=-1;
if(cnt2==1) nxt[t][x][d]=-2;
// cout<<t<<" "<<x<<" "<<d<<" --> "<<nxt[t][x][d]<<endl;
continue;
}
vector <int> vec;
vec.clear();
for(int i=0;i<=x;i++) vec.pb(g[1][i]);
for(int i=x+1;i<m;i++) vec.pb(g[0][i]);
nxt[t][x][d]=gethsh(vec);
/* cout<<t<<" "<<x<<" "<<d<<" --> "<<nxt[t][x][d]<<endl;
for(int i=0;i<2;i++)
{
for(int j=0;j<m;j++) cout<<g[i][j]<<" ";
puts("");
}*/
}
}
int idx=0;
for(int mask=0;mask<(1<<m);mask++)
{
vector <int> vec;
vec.clear();
for(int i=0;i<m;i++)
{
if(mask&(1<<i)) vec.pb(1);
else vec.pb(0);
}
for(int i=0,x0=0,x1=1;i<m;i++)
{
int j=i;
while(j+1<m&&vec[j+1]==vec[i]) j++;
int now=(vec[i]%2==0?x0:x1);
if(vec[i]%2==0) x0+=2;
else x1+=2;
for(int l=i;l<=j;l++) vec[l]=now;
i=j;
}
int x=gethsh(vec);
if(x==-1) continue;
dp[idx][x]=(dp[idx][x]+1)%mod;
// cout<<"init "<<x<<endl;
}
int ans=0;
for(int i=2;i<=n;i++) for(int j=1;j<=m;j++)
{
idx^=1;
memset(dp[idx],0,sizeof(dp[idx]));
for(int mask=1;mask<=cnt;mask++) if(dp[idx^1][mask]) for(int d=0;d<2;d++)
{
int mask2=nxt[mask][j-1][d];
if(mask2==-1) continue;
if(mask2==-2) ans=(ans+dp[idx^1][mask])%mod;
else dp[idx][mask2]=(dp[idx][mask2]+dp[idx^1][mask])%mod;
}
// cout<<i<<" "<<j<<" "<<ans<<endl;
// for(int mask=1;mask<=cnt;mask++) cout<<dp[idx][mask]<<" ";
// puts("");
}
// cout<<ans<<endl;
for(int mask=1;mask<=cnt;mask++)
{
bool Flg=0;
for(int j=0;j<m;j++) if(val[mask][j]>=2)
{
Flg=1;
break;
}
if(!Flg) ans=(ans+dp[idx][mask])%mod;
}
cout<<ans;
}
signed main()
{
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
【IOI2019】天桥
这篇题解很感性。
本题大体的思路是，选出一些尽可能少的点去做最短路。
先考虑 sub3，这个子任务中，显然一座桥一定从端点处上去或者从端点处下来。感性理解就是，所有高度都相等，不存在在某个位置能上去，走一段就上不去的情况。所以一条从中间离开并从中间上桥的路径可以进行简单的调整符合假设。
交上去发现有意外收获，过去了 sub4。
考虑 sub5 的情况，此时可能会有折返，也就是说我们需要特殊处理满足 \(L_i \le s \le R_i\) 和 \(L_i \le g \le R_i\) 的天桥，以 \(s\) 为例，找出 \(s\) 左边第一个在桥上的，和右边第一个在桥上的，以这两个点为分界点给桥裂成三段，这样左右两段都可以按 sub4 的方法处理，中间的那一段，由于长度为 \(2\)，也不会从中间上去或下来，\(g\) 同理，复杂度 \(O(n \log n)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int n,m,S,T;
int X[100005],H[100005];
int L[800005],R[800005],Y[800005];
vector <array<int,3> > P;
int vis[10000005],dis[10000005];
priority_queue <pii > pq;
vector <pii > g[10000005];
bool cmp1(pii x,pii y)
{
if(x.fi!=y.fi) return x.fi>y.fi;
return x.se<y.se;
}
void add(int u,int v,int w)
{
g[u].pb(mp(v,w)),g[v].pb(mp(u,w));
}
void build1()
{
vector <pii > vec;
vec.clear();
for(int i=1;i<=n;i++) vec.pb(mp(H[i],-i));
for(int i=1;i<=m;i++) vec.pb(mp(Y[i],i));
sort(vec.begin(),vec.end(),cmp1);
set <int> St;
St.clear();
for(int i=0;i<vec.size();i++)
{
if(vec[i].se<0) St.insert(-vec[i].se);
else
{
int j=vec[i].se;
auto it=St.lower_bound(L[j]);
while(1)
{
P.pb({X[*it],Y[j],P.size()+1});
if(*it==R[j]) break;
it++;
}
}
}
}
bool cmp2(array<int,3> x,array<int,3> y)
{
if(x[1]!=y[1]) return x[1]<y[1];
return x[0]<y[0];
}
void dij()
{
memset(dis,0x3f,sizeof(dis));
pq.push(mp(0LL,1LL));
dis[1]=0;
while(pq.size())
{
int u=pq.top().se;
pq.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i].fi;
if(dis[u]+g[u][i].se<dis[v]) dis[v]=dis[u]+g[u][i].se,pq.push(mp(-dis[v],v));
}
}
}
void build2()
{
vector <pii > vec;
vec.clear();
for(int i=1;i<=m;i++) vec.pb(mp(L[i],-i)),vec.pb(mp(R[i],i)),P.pb({X[L[i]],Y[i],P.size()+1}),P.pb({X[R[i]],Y[i],P.size()+1});
sort(vec.begin(),vec.end());
set <pii > St;
St.clear();
for(int i=0;i<vec.size();i++)
{
if(vec[i].se>0)
{
int j=i;
while(j+1<vec.size()&&vec[j+1].fi==vec[j].fi&&vec[j+1].se>0) j++;
for(int l=i;l<=j;l++)
{
auto it=St.lower_bound(mp(Y[vec[l].se],vec[l].se));
if(it!=St.begin()) it--,P.pb({X[vec[i].fi],(*it).fi,P.size()+1}),it++;
it++;
if(it!=St.end()) P.pb({X[vec[i].fi],(*it).fi,P.size()+1});
}
for(int l=i;l<=j;l++) St.erase(mp(Y[vec[l].se],vec[l].se));
i=j;
continue;
}
int j=i;
while(j+1<vec.size()&&vec[j+1].fi==vec[j].fi&&vec[j+1].se<0) j++;
for(int l=i;l<=j;l++) vec[l].se*=-1;
for(int l=i;l<=j;l++) St.insert(mp(Y[vec[l].se],vec[l].se));
for(int l=i;l<=j;l++)
{
auto it=St.lower_bound(mp(Y[vec[l].se],vec[l].se));
if(it!=St.begin()) it--,P.pb({X[vec[i].fi],(*it).fi,P.size()+1}),it++;
it++;
if(it!=St.end()) P.pb({X[vec[i].fi],(*it).fi,P.size()+1});
}
i=j;
}
}
void solve()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld%lld",&X[i],&H[i]);
for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&L[i],&R[i],&Y[i]),L[i]++,R[i]++;
scanf("%lld%lld",&S,&T);
S++,T++;
vector <pii > op;
op.clear();
for(int i=1;i<=n;i++) op.pb(mp(H[i],-i));
for(int i=1;i<=m;i++) op.pb(mp(Y[i],i));
sort(op.begin(),op.end(),cmp1);
set <int> St;
St.clear();
for(int i=0;i<op.size();i++)
{
if(op[i].se<0) St.insert(-op[i].se);
else
{
int x=op[i].se;
vector <int> vec;
vec.clear();
vec.pb(L[x]),vec.pb(R[x]);
auto it=St.lower_bound(S);
if(it!=St.end()&&L[x]<=(*it)&&(*it)<=R[x]) vec.pb(*it);
it=St.upper_bound(S);
if(it!=St.begin())
{
it--;
if(L[x]<=(*it)&&(*it)<=R[x]) vec.pb(*it);
}
it=St.lower_bound(T);
if(it!=St.end()&&L[x]<=(*it)&&(*it)<=R[x]) vec.pb(*it);
it=St.upper_bound(T);
if(it!=St.begin())
{
it--;
if(L[x]<=(*it)&&(*it)<=R[x]) vec.pb(*it);
}
sort(vec.begin(),vec.end());
for(int j=0,c=0;j+1<vec.size();j++)
{
if(vec[j]==vec[j+1]) continue;
if(c==0)
{
c=1;
L[x]=vec[j],R[x]=vec[j+1];
}
else
{
m++,Y[m]=Y[x],L[m]=vec[j],R[m]=vec[j+1];
// cout<<"... "<<m<<" "<<vec[j]<<" "<<vec[j+1]<<" "<<L[m]<<" "<<R[m]<<endl;
}
}
}
}
// for(int i=1;i<=n;i++) cout<<H[i]<<" "<<tmpH[i]<<endl;
// puts("");
P.pb({X[S],0LL,1});
build2();
P.pb({X[T],0LL,P.size()+1});
sort(P.begin(),P.end());
for(int i=0;i<P.size();i++)
{
int j=i;
while(j+1<P.size()&&P[j+1][0]==P[j][0]) j++;
int lst=-1;
for(int l=i;l<=j;l++)
{
int pos=lower_bound(X+1,X+1+n,P[l][0])-X;
if(P[l][1]>H[pos]) break;
if(lst!=-1) add(P[lst][2],P[l][2],abs(P[l][1]-P[lst][1]));
lst=l;
}
i=j;
}
vector <array<int,3> > vb;
vb.clear();
for(int i=1;i<=m;i++) vb.pb({Y[i],X[L[i]],X[R[i]]});
sort(vb.begin(),vb.end());
sort(P.begin(),P.end(),cmp2);
for(int i=0;i<P.size();i++)
{
int j=i;
while(j+1<P.size()&&P[j+1][1]==P[j][1]) j++;
for(int l=i;l<j;l++)
{
if(P[l][0]==P[l+1][0])
{
add(P[l][2],P[l+1][2],0LL);
continue;
}
array<int,3> Tp={P[l][1],P[l][0]+1,-1LL};
int pos=lower_bound(vb.begin(),vb.end(),Tp)-vb.begin()-1;
if(pos<0) continue;
if(vb[pos][0]!=P[l][1]) continue;
if(!(vb[pos][1]<=P[l][0]&&P[l+1][0]<=vb[pos][2])&&P[l][0]!=P[l+1][0]) continue;
add(P[l][2],P[l+1][2],abs(P[l][0]-P[l+1][0]));
}
i=j;
}
dij();
int ans=dis[P.size()];
if(ans>INF) ans=-1;
printf("%lld\n",ans);
}
signed main()
{
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
【WF2017】Replicate Replicate Rfplicbte
考虑推出前一个状态。
假设没有 bug，令 \(A_{i,j}\) 为现状态，\(B_{i,j}\) 为原状态，手玩发现，我们可以从上往下从左往右还原 \(B\)，\(B_{i,j}=A_{i,j } \space \text{xor} \space _{0 \le x,y \le 2 , x+y \neq 0} B_{i-x,j-y}\)。
若没有 bug，则 \(B\) 的后两行后两列均为 \(0\)，如果有 bug，把 bug 影响到的位置打表打出来，可以发现 bug 只可能存在于，后两行中第一个 \(1\) 所在列，和后两列中第一个 \(1\) 所在行，的交点。找出它后重算就行，复杂度 \(O(n^3)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int n,m;
int a[305][305],b[305][305];
void calcb()
{
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
{
b[i][j]=0;
b[i][j]^=b[i-1][j]^b[i][j-1]^b[i-1][j-1];
if(i>=2) b[i][j]^=b[i-2][j]^b[i-2][j-1];
if(j>=2) b[i][j]^=b[i][j-2]^b[i-1][j-2];
if(i>=2&&j>=2) b[i][j]^=b[i-2][j-2];
b[i][j]^=a[i][j];
}
/* puts("tried");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) cout<<b[i][j];
puts("");
}
system("pause");*/
}
bool valid()
{
for(int i=1;i<=m;i++) if(b[n-1][i]||b[n][i]) return 0;
for(int i=1;i<=n;i++) if(b[i][m-1]||b[i][m]) return 0;
return 1;
}
void moveA()
{
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=b[i][j];
/* for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) cout<<a[i][j];
puts("");
}*/
int dx=0,dy=0;
for(int i=1;i<=n;i++)
{
bool Flg=0;
for(int j=1;j<=m;j++) if(a[i][j]) Flg=1;
if(Flg) break;
dx++;
}
for(int j=1;j<=m;j++)
{
bool Flg=0;
for(int i=1;i<=n;i++) if(a[i][j]) Flg=1;
if(Flg) break;
dy++;
}
n-=dx,m-=dy;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=a[i+dx][j+dy];
while(1)
{
if(!n||!m) break;
bool Flg=0;
for(int j=1;j<=m;j++) if(a[n][j]) Flg=1;
if(!Flg) n--;
if(!n||!m) break;
bool Flg2=0;
for(int i=1;i<=n;i++) if(a[i][m]) Flg2=1;
if(!Flg2) m--;
if(!n||!m) break;
if(Flg&&Flg2) break;
}
/* for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) cout<<a[i][j];
puts("");
}
system("pause");*/
}
void solve()
{
cin>>n>>m;
swap(n,m);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
{
char ch;
cin>>ch;
a[i][j]=(ch=='#'?1:0);
}
while(1)
{
if(n<=2||m<=2) break;
// puts("......");
calcb();
if(valid())
{
moveA();
continue;
}
bool Flg=0;
int X=1,Y=1;
while(Y<=m&&b[n-1][Y]==0&&b[n][Y]==0) Y++;
while(X<=n&&b[X][m-1]==0&&b[X][m]==0) X++;
for(int dx=0;dx<=0;dx++)
{
for(int dy=0;dy<=0;dy++)
{
int i=X+dx,j=Y+dy;
if(i>n||j>m||i<1||j<1) continue;
a[i][j]^=1;
calcb();
if(valid())
{
moveA();
Flg=1;
// cout<<i<<" "<<j<<endl;
break;
}
a[i][j]^=1;
}
if(Flg) break;
}
if(!Flg) break;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) cout<<(a[i][j]?'#':'.');
puts("");
}
}
signed main()
{
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
【LOJ511】验题
对于这种字典序问题，考虑枚举 lcp，找到合适的 lcp 后不断枚举下一个数。
考虑钦定一部分点（选或不选）算独立集个数，这个可以用朴素的 \(O(n)\) dp 解决，不再赘述。
我们需要支持：修改一个点的钦定状态，查询独立集的个数，此时可以直接暴力 ddp 维护矩阵乘法，当然也有更优美的解法：
一个点钦定不选，可以直接删掉；一个点钦定选择，相当于删掉它和它的邻居。
剩下的点如果不超过 \(120\)，考虑二分图染色，令较小的一侧每个点不选，较大的一侧每个点都可以自由选择，至少有 \(2^{60} \gt 10^{18}\) 个独立集，当然这个下界，肯定可以更优。
仔细考虑修改的过程，每个点只会被修改 \(O(1)\) 次，可以暴力枚举它的邻居，用 set 维护现存没被删的节点，复杂度 \(O(n \log k)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define i128 __int128
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18+5;
int dp[1000005][2];
int tag[1000005],ok[1000005],inS[1000005];
vector <int> g[1000005];
void dfs(int u,int fa)
{
dp[u][0]=dp[u][1]=1;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==fa) continue;
dfs(v,u);
i128 t=(i128)(dp[u][0])*(i128)(dp[v][0]+dp[v][1]);
if(t>(i128)(INF)) t=INF;
dp[u][0]=(int)(t);
t=(i128)(dp[u][1])*(i128)(dp[v][0]);
if(t>(i128)(INF)) t=INF;
dp[u][1]=(int)(t);
}
if(tag[u]==0) dp[u][1]=0;
if(tag[u]==1) dp[u][0]=0;
// cout<<u<<" "<<dp[u][0]<<" "<<dp[u][1]<<endl;
}
int n,m,k;
set <int> St;
int cnt[1000005];
void update(int id,int x)
{
if(tag[id]<=1)
{
cnt[id]--;
if(!cnt[id]) St.insert(id);
}
if(tag[id]==1)
{
for(int i=0;i<g[id].size();i++)
{
cnt[g[id][i]]--;
if(!cnt[g[id][i]]) St.insert(g[id][i]);
}
}
tag[id]=x;
if(tag[id]<=1)
{
cnt[id]++;
if(cnt[id]==1) St.erase(id);
}
if(tag[id]==1)
{
for(int i=0;i<g[id].size();i++)
{
cnt[g[id][i]]++;
if(cnt[g[id][i]]==1) St.erase(g[id][i]);
}
}
}
void dfs(int u)
{
dp[u][0]=dp[u][1]=1;
ok[u]=1;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(ok[v]) continue;
if(!inS[v]) continue;
dfs(v);
i128 t=(i128)(dp[u][0])*(i128)(dp[v][0]+dp[v][1]);
if(t>(i128)(INF)) t=INF;
dp[u][0]=(int)(t);
t=(i128)(dp[u][1])*(i128)(dp[v][0]);
if(t>(i128)(INF)) t=INF;
dp[u][1]=(int)(t);
}
if(tag[u]==0) dp[u][1]=0;
if(tag[u]==1) dp[u][0]=0;
}
int calc()
{
if(St.size()>=120) return INF;
int ans=1;
for(auto it=St.begin();it!=St.end();it++) inS[*it]=1;
for(auto it=St.begin();it!=St.end();it++) if(!ok[(*it)])
{
int u=(*it);
dfs(u);
i128 t=(i128)(ans)*(i128)(dp[u][0]+dp[u][1]);
if(t>(i128)(INF)) t=INF;
ans=(int)(t);
}
for(auto it=St.begin();it!=St.end();it++) ok[*it]=inS[*it]=0;
return ans;
}
int S[1000005],U[1000005],V[1000005];
void solve()
{
cin>>n>>k;
for(int i=1;i<=n;i++) tag[i]=2,St.insert(i);
for(int i=1;i<n;i++) cin>>U[i];
for(int i=1;i<n;i++) cin>>V[i],g[U[i]+1].pb(V[i]+1),g[V[i]+1].pb(U[i]+1);
cin>>m;
for(int i=1;i<=m;i++) cin>>S[i],S[i]++;
sort(S+1,S+1+m);
for(int i=1;i<=S[m];i++) update(i,0);
for(int i=1;i<=m;i++) update(S[i],1);
int j=m,lst=n;
while(1)
{
int tmp=calc()-1;
if(j&&tmp<k)
{
k-=tmp;
for(int i=S[j]+1;i<=lst;i++) update(i,2);
update(S[j],0),lst=S[j],j--;
}
else
{
if(lst==n) lst=S[j];
lst++;
// cout<<"...... "<<j<<" "<<lst<<" "<<k<<endl;
while(lst<=n)
{
bool inv=0;
for(int i=0;i<g[lst].size();i++) if(tag[g[lst][i]]==1)
{
inv=1;
break;
}
if(inv)
{
update(lst,0);
lst++;
continue;
}
update(lst,1);
tmp=calc();
// cout<<lst<<" "<<tmp<<endl;
// for(int i=1;i<=n;i++) cout<<tag[i]<<" ";
// puts("");
if(tmp<k)
{
k-=tmp;
update(lst,0);
lst++;
continue;
}
S[++j]=lst;
k--,lst++;
if(!k) break;
}
for(int i=1;i<=j;i++) cout<<S[i]-1<<" ";
return;
}
}
}
signed main()
{
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
【MEX Foundation Contest】The Jump from Height of Self-importance to Height of IQ Level
显然可以用 fhq-treap 搞定，考虑维护什么。
- 子树内最大值和最小值，子树大小。
- 子树内是否已经存在三个 \(i,j,k\) 满足条件。
- 对于子树内所有 \(i \lt j\) 且 \(h_i \lt h_j\) 中，\(h_j\) 的最小值和 \(h_i\) 的最大值。
前两条很容易想到，第三条要维护是因为在 pushup 的时候会在某一棵子树内形成长度为 \(2\) 的链。
前两条的 pushup 是容易的，第三条可能有点麻烦，也需要一点人类智慧，以 \(h_j\) 的最小值为例。
- 先把左右两边的 \(h_j\) 最小值算上。
- 取左子树的 \(\min\)，记为 \(lim\)，在右子树中找 \(\min\) 的后继，令目前所在节点的值为 \(val\)。
- 若 \(val \gt lim\)，则更新结果，此时若左子树存在更优的数，即左子树中存在 \(x\) 满足 \(lim \lt x \lt val\)，会发现已经满足了题目中的条件，不必在左子树中找了。
- 若 \(val \lt lim\)，此时若柚子树中存在合法的数，即右子树中存在 \(y\) 满足 \(lim \lt y\)，此时 \(val \lt y\)，这种情况已经涵盖在了右子树的答案中，不必在右子树中找了。
pushup 的复杂度是 \(O(\log n)\)，总复杂度是大常数的 \(O(n \log^2 n)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
mt19937 rnd(114514);
int ls[120005],rs[120005],sz[120005],w[120005],maxx[120005],minn[120005],min2[120005],max2[120005],val[120005];
bool ok[120005];
void pushup(int id)
{
sz[id]=sz[ls[id]]+sz[rs[id]]+1;
maxx[id]=max(maxx[ls[id]],max(maxx[rs[id]],val[id]));
minn[id]=min(minn[ls[id]],min(minn[rs[id]],val[id]));
ok[id]=ok[ls[id]]|ok[rs[id]];
if(minn[ls[id]]<val[id]&&val[id]<maxx[rs[id]]) ok[id]=1;
if(min2[ls[id]]<max(val[id],maxx[rs[id]])) ok[id]=1;
if(min(minn[ls[id]],val[id])<max2[rs[id]]) ok[id]=1;
min2[id]=min(min2[ls[id]],min2[rs[id]]);
if(minn[ls[id]]<val[id]) min2[id]=min(min2[id],val[id]);
int u=rs[id];
while(u)
{
if(val[u]>min(val[id],minn[ls[id]])) min2[id]=min(min2[id],val[u]);
if(val[u]>min(val[id],minn[ls[id]])) u=rs[u];
else u=ls[u];
}
max2[id]=max(max2[ls[id]],max2[rs[id]]);
if(val[id]<maxx[rs[id]]) max2[id]=max(max2[id],val[id]);
u=ls[id];
while(u)
{
if(val[u]<max(val[id],maxx[rs[id]])) max2[id]=max(max2[id],val[u]);
if(val[u]<max(val[id],maxx[rs[id]])) u=ls[u];
else u=rs[u];
}
}
int newnode(int id,int v)
{
val[id]=maxx[id]=minn[id]=v;
sz[id]=1,w[id]=rnd();
return id;
}
void split(int id,int k,int &x,int &y)
{
if(!id)
{
x=y=0;
return;
}
if(sz[ls[id]]<k) x=id,split(rs[id],k-sz[ls[id]]-1,rs[id],y);
else y=id,split(ls[id],k,x,ls[id]);
pushup(id);
}
int merge(int x,int y)
{
if(!x||!y) return max(x,y);
if(w[x]<w[y])
{
rs[x]=merge(rs[x],y);
pushup(x);
return x;
}
else
{
ls[y]=merge(x,ls[y]);
pushup(y);
return y;
}
}
void print(int id)
{
cout<<id<<": "<<ls[id]<<" "<<rs[id]<<" "<<sz[id]<<" "<<maxx[id]<<" "<<minn[id]<<" "<<max2[id]<<" "<<min2[id]<<" "<<ok[id]<<endl;
if(ls[id]) print(ls[id]);
if(rs[id]) print(rs[id]);
}
int n,a[120005],Q;
void solve()
{
memset(maxx,-0x3f,sizeof(maxx)),memset(minn,0x3f,sizeof(minn));
memset(max2,-0x3f,sizeof(max2)),memset(min2,0x3f,sizeof(min2));
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int rt=newnode(1,a[1]);
for(int i=2;i<=n;i++)
{
int x=newnode(i,a[i]);
rt=merge(rt,x);
}
// print(rt);
// system("pause");
// puts(ok[rt]?"YES":"NO");
cin>>Q;
while(Q--)
{
int l,r,k;
cin>>l>>r>>k;
int s=r-l+1-k;
int u,v,x,y;
split(rt,l-1,u,v);
split(v,s,v,x);
split(x,k,x,y);
rt=merge(u,merge(x,merge(v,y)));
puts(ok[rt]?"YES":"NO");
}
}
signed main()
{
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}