前言
今天不知道为啥去打 MX 了，bug 不少啊，包括但不限于赛时能通过自己主页看自己题过没过，赛时可以进入“补题”的比赛交从而直接成 IOI 赛制，文件还有点问题？
0+100+12+0，T1 读假题：\(\ge×，>√\)，喜提爆零，但是本来就不会正解，我去我表都打出来了不知道二分？？！？！！？
不打 T4 是错误的，乱搞能得的分挺多的。
T2 是签，线段树直接跑就行了，行为是值域线段树所以从 \(0\) 开始，结果查询的时候忘了还是从 \(1\) 开始的，唐了好长时间，然后因为有 \(0\)，所以不能用查理线段树。
下午到机房不知道为啥困得快死了，在机房睡了不知道多长时间。
T1 邻间的骰子之舞
设 \(x\) 表示复制，\(y\) 表示粘贴，打表或者基本不等式证一下，则最优解一定是形如 \(x~k\cdot y~x~k\cdot y…x~(k-1)\cdot y~x~(k-1)\cdot y…\) 的形式，发现 \(x\) 的个数 \(\le\log_2(n)\)，可以直接枚举，\(k\) 则可以直接二分，再枚举 \(k\) 和 \(k-1\) 的断点，复杂度 \(O(\log^3)\)，发现每次都枚举 \(k\) 是唐氏，改成 \(O(\log^2)\) 的。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define ull __int128
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e6+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar_unlocked();
for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
ll n; int m; ull x,y,ans=1e27;
inline bool check(int x,ll y)
{ull res=1; while(x--) {res*=y; if(res>n) return 1;} return 0;}
inline ull qpow(ull a,int b)
{ull res=1; for(;b;a*=a,b>>=1) (b&1)&&(res*=a); return res;}
signed main()
{
freopen("dice.in","r",stdin),freopen("dice.out","w",stdout);
read(n,x,y),m=log2(n)+1;
for(int i=1;i<=m;i++)
{
ll l=0,r=n,mid,res;
while(l<=r) check(i,(mid=l+r>>1)+1)?r=(res=mid)-1:l=mid+1;
ull sum=qpow(res,i); for(int j=1;j<=i;j++)
{
sum/=res,sum*=(res+1);
sum>n&&(ans=min(ans,(x+(res-1)*y)*i+y*j));
}
}
write(ans);
}
T2 星海浮沉录
对于一个值 \(pre_i\)，表示 \(i\) 距离上一个 \(a_i\) 出现位置的距离，那么若存在 \(pre_i>x\) 则 \(a_i\) 就可能成为 \(mex\)，那么对于每一个权值维护其最大的 \(pre\)，最后在线段树上跑二分找到最小的 \(a_i\) 满足 \(pre_i>a_i\) 即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define mid (l+r>>1)
#define ls (p<<1)
#define rs (p<<1|1)
#define pb push_back
using namespace std;
const int N=1e6+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar_unlocked();
for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,a[N],rk[N],pre[N],now[N]; vector<int>e[N],pos[N];
struct private_tree
{
vector<int>mx;
inline void build(int p,int l,int r,int x)
{
if(l==r) return mx[p]=pre[e[x][l-1]],void();
build(ls,l,mid,x),build(rs,mid+1,r,x),mx[p]=max(mx[ls],mx[rs]);
}
inline void init(int x,int siz) {mx.resize((siz+5)<<2),build(1,1,siz,x);}
inline void change(int p,int l,int r,int x,int d)
{
if(l==r) return mx[p]=d,void();
x<=mid?change(ls,l,mid,x,d):change(rs,mid+1,r,x,d);
mx[p]=max(mx[ls],mx[rs]);
}
}t[N];
struct total_tree
{
int mx[N<<2];
inline void build(int p,int l,int r)
{
if(l==r) return mx[p]=t[l].mx[1],void();
build(ls,l,mid),build(rs,mid+1,r),mx[p]=max(mx[ls],mx[rs]);
}
inline void change(int p,int l,int r,int x,int d)
{
if(l==r) return mx[p]=d,void();
x<=mid?change(ls,l,mid,x,d):change(rs,mid+1,r,x,d);
mx[p]=max(mx[ls],mx[rs]);
}
inline int ask(int p,int l,int r,int x)
{
if(l==r) return l;
if(mx[ls]>=x) return ask(ls,l,mid,x);
if(mx[rs]>=x) return ask(rs,mid+1,r,x);
return n+1;
}
}T;
signed main()
{
freopen("star.in","r",stdin),freopen("star.out","w",stdout);
read(n,m); for(int i=1;i<=n;i++)
read(a[i]),pre[i]=i-now[a[i]]-1,e[a[i]].pb(now[a[i]]=i);
for(int i=0;i<=n;i++)
pre[n+i+1]=n-now[i],e[i].pb(n+i+1),t[i].init(i,e[i].size());
T.build(1,0,n); for(int i=0;i<=n;i++)
{
pos[i].pb(0); for(int j=0;j<e[i].size();j++)
rk[e[i][j]]=j+1,pos[i].pb(e[i][j]);
}
for(int op,x;m;m--)
{
read(op,x); if(op==1)
{
if(a[x]==a[x+1]) continue;
t[a[x]].change(1,1,e[a[x]].size(),rk[x],++pre[x]);
t[a[x]].change(1,1,e[a[x]].size(),rk[x]+1,--pre[pos[a[x]][rk[x]+1]]);
T.change(1,0,n,a[x],t[a[x]].mx[1]);
t[a[x+1]].change(1,1,e[a[x+1]].size(),rk[x+1],--pre[x+1]);
t[a[x+1]].change(1,1,e[a[x+1]].size(),rk[x+1]+1,++pre[pos[a[x+1]][rk[x+1]+1]]);
T.change(1,0,n,a[x+1],t[a[x+1]].mx[1]);
swap(pos[a[x]][rk[x]],pos[a[x+1]][rk[x+1]]);
swap(a[x],a[x+1]),swap(rk[x],rk[x+1]),swap(pre[x],pre[x+1]);
}
else write(T.ask(1,0,n,x)),puts("");
}
}
T3 勾指起誓
高级多项式题，再见。
T4 第八交响曲
双调排序。
对于一个单峰序列，设 \(n=2^k\)，对于 \(i\in [1,2^{k-1}]\) 执行一次 \((i,i+2^{k-1})\) 操作，则序列会变成一个满足 \(\forall i\in[1,2^{k-1}],j\in [2^{k-1}+1,2^k],a_i<a_j\) 的两个单峰序列。
那么对于一个乱序的序列，假设可以将他变成两个有序序列，考虑合并两个有序序列，发现只有把有区间的所有数翻转就和上面一样了，于是就可以递归求解了，复杂度 \(O(\frac{k(k+1)}{2})\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
using namespace std;
const int N=110;
int n,ans,pos1[N],pos2[N][N]; vector<pair<int,int> >e[N];
inline void solve2(int l,int r,int dep,int top)
{
if(l==r) return ; int mid=l+r>>1;
if(!pos2[top][dep]) pos2[top][dep]=++ans;
for(int i=l,j=mid+1;j<=r;i++,j++) e[pos2[top][dep]].pb(mkp(i,j));
solve2(l,mid,dep+1,top),solve2(mid+1,r,dep+1,top);
}
inline void solve1(int l,int r,int dep)
{
if(l==r) return ; int mid=l+r>>1;
solve1(l,mid,dep+1),solve1(mid+1,r,dep+1);
if(!pos1[dep]) pos1[dep]=++ans;
for(int i=l,j=r;j>mid;i++,j--) e[pos1[dep]].pb(mkp(i,j));
solve2(l,mid,dep+1,dep),solve2(mid+1,r,dep+1,dep);
}
signed main()
{
freopen("symphony.in","r",stdin),freopen("symphony.out","w",stdout);
scanf("%d",&n); int tmp=n; n=powl(2,ceil(log2(n)));
solve1(1,n,1),printf("%d\n",ans);
for(int i=1;i<=ans;i++,puts("")) for(auto j:e[i])
if(j.fi<=tmp&&j.se<=tmp) printf("CMPSWP R%d R%d ",j.fi,j.se);
}