NOI2021山东省队二轮集训
模拟赛
Day 1
第一天，状态奇差，T1算错复杂度，\(O(n\log n)\) 被卡到 \(50pts\)，本来可以胡乱写一个 \(O(n\log \log n)\) 的；T2和T3暴力都不会打，T2暴力调了很久，虽然过了样例但是WA掉了；T3冲了一发倍增套线段树合并，复杂度不知道，空间似乎也炸，也没调出来。直接垫底了……
T1
答案 \(\leq \log n+1\)，因为总共只有 \(O(n)\) 个子串。二分答案可以做到 \(O(n\log \log n)\)。考虑先把 \(\log n+1\) 层的算出来，相当于是去求一个 \(mex\)；然后把所有数除以二再求 \(mex\)，……。每一次去重之后复杂度就是 \(O(n)\) 了，还可以用 bitset 优化到 \(\frac{n}{w}\)。
点击查看代码
#include
#include
#define re register
#define rint re int
using namespace std;
const int N=16777216+13;
int a[N],n,ans[N];
bool b[N<<1];
inline void rd(){
re char c=getchar();
while(c!='0'&&c!='1') c=getchar();
while(c=='0'||c=='1') a[++n]=c-'0',c=getchar();
}
int main(){
rd();
rint lim=0,limit=1;
while(limit>1]|=b[i];
if(i) b[i]=0;
}
rint tmp=0;
--lim;
for(rint i=n-lim+1;i<=n;++i) tmp=(tmp<<1|a[i]);
b[tmp]|=1;
}
rint j=0;
while(las) ans[++j]=(las&1),las>>=1;
for(rint i=lim+1;i>=1;--i) putchar(ans[i]?'1':'0');
return 0;
}
T2 P6106
答案满足可减，首先把一个 4-side 矩形化成四个 2-side 矩形。先考虑 \(k>0\) 的线段，可以分成四类：在矩形内、与上边界有交、与右边界有交、完全在外面。通过维护左右端点可以快速分类。对于与边界有交的两类，由于线段不交，所以可以扫描线，维护一个类似于导数的东西，极小增量的时候每个线段对答案的贡献和。斜率为负的直线就反过来跑一遍，复杂度是常数比较大的 \(O(n\log n)\)。
T3
建完虚树之后，可以把答案拆成 \(O(k)\) 个段的总贡献。可以去枚举两个段的贡献，是 \(O(k^2)\) 的。然后可以把这个东西搞一个树上差分，就可以四维莫队变二维莫队了。还有一个做法是两次根号分治？
Day 2
自闭了，T1被卡常，T2最后一个小时写了300行线段树，维护了二十多个信息，没调出来，T3没怎么看……直接垫底。
T1
环套树森林，考虑二分答案。把所有点权都减一个 \(ans\)，环缩成一个点一样处理，拓扑排序时跑dp就可以了。注意可以先把拓扑序求出来，然后直接在上面dp。被卡常了。
点击查看代码
#include
#include
#include
#include
#include
#define re register
#define rint re int
#define rll re ll
using namespace std;
inline int rd(){
rint res=0,flag=1;re char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')flag=-1;
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res*flag;
}
inline int min(const int &a,const int &b){return am) return 0;
}
return sum<=m;
}
inline void solve(){
rll l=1e8,r=0;
for(rint i=1;i<=n;++i) l=min(l,a[i]),r+=a[i];
r=(r+m)/n;
while(l>1;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%lld\n",l);
}
int main(){
n=rd(),m=rd();
for(rint i=1,x;i<=n;++i){
fa[i]=rd();
if(fa[i]!=-1&&fa[i]!=i) Tarjan::add(i,fa[i]);
}
for(rint i=1;i<=n;++i) a[i]=rd();
for(rint i=1;i<=n;++i)
if(!Tarjan::dfn[i]) tarjan(i);
for(rint i=1;i<=n;++i)
if(fa[i]!=-1&&fa[i]!=i) add(c[i],c[fa[i]]),tmpind[c[fa[i]]]++;
solve();
return 0;
}
T2
枚举右端点，线段树维护左端点的 \(max-min\)，加上中间变量需要维护 \(7\) 个值。每个点的区间相当于是一个矩形，然后从左到右扫描线做这个东西？单调栈可以维护一下 \(max\) 和 \(min\)，复杂度是大常数的 \(O(n\log n)\)。没调出来！！
点击查看代码
#include
#include
#include
using namespace std;
inline int max(const int &a,const int &b){return a>b?a:b;}
inline int min(const int &a,const int &b){return a>1)
inline void refresh(int p){t[p].x=t[ls].x+t[rs].x;}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r) return t[p].x=(data){(uint)a[l],(uint)b[l],(uint)c[l],(uint)a[l]*b[l],(uint)a[l]*c[l],(uint)b[l]*c[l],(uint)a[l]*b[l]*c[l]},void();
build(ls,l,mid),build(rs,mid+1,r);
refresh(p);
}
data query(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r) return t[p].x;
if(r<=mid) return query(ls,l,r);
if(l>mid) return query(rs,l,r);
return query(ls,l,r)+query(rs,l,r);
}
#undef mid
void main(){
build(1,1,n);
uint sum=0;
for(int i=2;i<=n;++i){
data tmp=query(1,1,i-1);
sum+=(uint)a[i]*b[i]*c[i]*(i-1)-(uint)a[i]*b[i]*tmp.sum_c-(uint)a[i]*c[i]*tmp.sum_b-(uint)b[i]*c[i]*tmp.sum_a+(uint)a[i]*tmp.sum_bc+(uint)b[i]*tmp.sum_ac+(uint)c[i]*tmp.sum_ab-tmp.sum_abc;
}
cout<>1)
inline void refresh(int p){
t[p].x=t[ls].x+t[rs].x;
t[p].a1=t[ls].a1+t[rs].a1;
t[p].a2=t[ls].a2+t[rs].a2;
t[p].b1=t[ls].b1+t[rs].b1;
t[p].b2=t[ls].b2+t[rs].b2;
t[p].c1=t[ls].c1+t[rs].c1;
t[p].c2=t[ls].c2+t[rs].c2;
t[p].a1b1=t[ls].a1b1+t[rs].a1b1;
t[p].a1b2=t[ls].a1b2+t[rs].a1b2;
t[p].a1c1=t[ls].a1c1+t[rs].a1c1;
t[p].a1c2=t[ls].a1c2+t[rs].a1c2;
t[p].a2b1=t[ls].a2b1+t[rs].a2b1;
t[p].a2b2=t[ls].a2b2+t[rs].a2b2;
t[p].a2c1=t[ls].a2c1+t[rs].a2c1;
t[p].a2c2=t[ls].a2c2+t[rs].a2c2;
t[p].b1c1=t[ls].b1c1+t[rs].b1c1;
t[p].b1c2=t[ls].b1c2+t[rs].b1c2;
t[p].b2c1=t[ls].b2c1+t[rs].b2c1;
t[p].b2c2=t[ls].b2c2+t[rs].b2c2;
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r) return;
build(ls,l,mid),build(rs,mid+1,r);
}
inline void pushup_maxa(int p,int x){
t[p].seta1=x;t[p].a1=(uint)x*(t[p].r-t[p].l+1);
t[p].a1b1=(uint)x*t[p].b1;
t[p].a1b2=(uint)x*t[p].b2;
t[p].a1c1=(uint)x*t[p].c1;
t[p].a1c2=(uint)x*t[p].c2;
t[p].x.a1_b1_c1=(uint)x*t[p].b1c1;
t[p].x.a1_b1_c2=(uint)x*t[p].b1c2;
t[p].x.a1_b2_c1=(uint)x*t[p].b2c1;
t[p].x.a1_b2_c2=(uint)x*t[p].b2c2;
}
inline void pushup_mina(int p,int x){
t[p].seta2=x;t[p].a2=(uint)x*(t[p].r-t[p].l+1);
t[p].a2b1=(uint)x*t[p].b1;
t[p].a2b2=(uint)x*t[p].b2;
t[p].a2c1=(uint)x*t[p].c1;
t[p].a2c2=(uint)x*t[p].c2;
t[p].x.a2_b1_c1=(uint)x*t[p].b1c1;
t[p].x.a2_b1_c2=(uint)x*t[p].b1c2;
t[p].x.a2_b2_c1=(uint)x*t[p].b2c1;
t[p].x.a2_b2_c2=(uint)x*t[p].b2c2;
}
inline void pushup_maxb(int p,int x){
t[p].setb1=x;t[p].b1=(uint)x*(t[p].r-t[p].l+1);
t[p].a1b1=(uint)x*t[p].a1;
t[p].a2b1=(uint)x*t[p].a2;
t[p].b1c1=(uint)x*t[p].c1;
t[p].b1c2=(uint)x*t[p].c2;
t[p].x.a1_b1_c1=(uint)x*t[p].a1c1;
t[p].x.a1_b1_c2=(uint)x*t[p].a1c2;
t[p].x.a2_b1_c1=(uint)x*t[p].a2c1;
t[p].x.a2_b1_c2=(uint)x*t[p].a2c2;
}
inline void pushup_minb(int p,int x){
t[p].setb2=x;t[p].b2=(uint)x*(t[p].r-t[p].l+1);
t[p].a1b2=(uint)x*t[p].a1;
t[p].a2b2=(uint)x*t[p].a2;
t[p].b2c1=(uint)x*t[p].c1;
t[p].b2c2=(uint)x*t[p].c2;
t[p].x.a1_b2_c1=(uint)x*t[p].a1c1;
t[p].x.a1_b2_c2=(uint)x*t[p].a1c2;
t[p].x.a2_b2_c1=(uint)x*t[p].a2c1;
t[p].x.a2_b2_c2=(uint)x*t[p].a2c2;
}
inline void pushup_maxc(int p,int x){
t[p].setc1=x;t[p].c1=(uint)x*(t[p].r-t[p].l+1);
t[p].a1c1=(uint)x*t[p].a1;
t[p].a2c1=(uint)x*t[p].a2;
t[p].b1c1=(uint)x*t[p].b1;
t[p].b2c1=(uint)x*t[p].b2;
t[p].x.a1_b1_c1=(uint)x*t[p].a1b1;
t[p].x.a1_b2_c1=(uint)x*t[p].a1b2;
t[p].x.a2_b1_c1=(uint)x*t[p].a2b1;
t[p].x.a2_b2_c1=(uint)x*t[p].a2b2;
}
inline void pushup_minc(int p,int x){
t[p].setc2=x;t[p].c2=(uint)x*(t[p].r-t[p].l+1);
t[p].a1c2=(uint)x*t[p].a1;
t[p].a2c2=(uint)x*t[p].a2;
t[p].b1c2=(uint)x*t[p].b1;
t[p].b2c2=(uint)x*t[p].b2;
t[p].x.a1_b1_c2=(uint)x*t[p].a1b1;
t[p].x.a1_b2_c2=(uint)x*t[p].a1b2;
t[p].x.a2_b1_c2=(uint)x*t[p].a2b1;
t[p].x.a2_b2_c2=(uint)x*t[p].a2b2;
}
inline void pushdown(int p){
if(t[p].seta1) pushup_maxa(ls,t[p].seta1),pushup_maxa(rs,t[p].seta1),t[p].seta1=0;
if(t[p].seta2) pushup_mina(ls,t[p].seta2),pushup_mina(rs,t[p].seta2),t[p].seta2=0;
if(t[p].setb1) pushup_maxb(ls,t[p].setb1),pushup_maxb(rs,t[p].setb1),t[p].setb1=0;
if(t[p].setb2) pushup_minb(ls,t[p].setb2),pushup_minb(rs,t[p].setb2),t[p].setb2=0;
if(t[p].setc1) pushup_maxc(ls,t[p].setc1),pushup_maxc(rs,t[p].setc1),t[p].setc1=0;
if(t[p].setc2) pushup_minc(ls,t[p].setc2),pushup_minc(rs,t[p].setc2),t[p].setc2=0;
}
void setmaxa(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r) return pushup_maxa(p,x);
pushdown(p);
if(l<=mid) setmaxa(ls,l,r,x);
if(r>mid) setmaxa(rs,l,r,x);
refresh(p);
}
void setmina(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r) return pushup_mina(p,x);
pushdown(p);
if(l<=mid) setmina(ls,l,r,x);
if(r>mid) setmina(rs,l,r,x);
refresh(p);
}
void setmaxb(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r) return pushup_maxb(p,x);
pushdown(p);
if(l<=mid) setmaxb(ls,l,r,x);
if(r>mid) setmaxb(rs,l,r,x);
refresh(p);
}
void setminb(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r) return pushup_minb(p,x);
pushdown(p);
if(l<=mid) setminb(ls,l,r,x);
if(r>mid) setminb(rs,l,r,x);
refresh(p);
}
void setmaxc(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r) return pushup_maxc(p,x);
pushdown(p);
if(l<=mid) setmaxc(ls,l,r,x);
if(r>mid) setmaxc(rs,l,r,x);
refresh(p);
}
void setminc(int p,int l,int r,int x){
if(l<=t[p].l&&t[p].r<=r) return pushup_minc(p,x);
pushdown(p);
if(l<=mid) setminc(ls,l,r,x);
if(r>mid) setminc(rs,l,r,x);
refresh(p);
}
data query(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r) return t[p].x;
pushdown(p);
if(r<=mid) return query(ls,l,r);
if(l>mid) return query(rs,l,r);
return query(ls,l,r)+query(rs,l,r);
}
#undef mid
void main(){
build(1,1,n);
stack upa,dna,upb,dnb,upc,dnc;
uint sum=0;
for(int i=1,tmp;i<=n;++i){
while(!upa.empty()&&a[upa.top()]a[i]) dna.pop();
tmp=1;if(!dna.empty()) tmp=dna.top()+1;
setmina(1,tmp,i,a[i]);dna.push(i);
while(!upb.empty()&&b[upb.top()]b[i]) dnb.pop();
tmp=1;if(!dnb.empty()) tmp=dnb.top()+1;
setminb(1,tmp,i,b[i]);dnb.push(i);
while(!upc.empty()&&c[upc.top()]c[i]) dnc.pop();
tmp=1;if(!dnc.empty()) tmp=dnc.top()+1;
setminc(1,tmp,i,c[i]);dnc.push(i);
data res=query(1,1,i);
sum+=res.a1_b1_c1-res.a1_b1_c2-res.a1_b2_c1-res.a2_b1_c1+res.a1_b2_c2+res.a2_b1_c2+res.a2_b2_c1-res.a2_b2_c2;
}
cout< T3
可以用 \(\log v\) 段的分段函数维护这个 \(O(v)\) 的东西。这是个指数级的东西，还是考虑使用可持久化平衡树维护区间复制和区间翻转，这样就可以做 \(l=1,r=n\) 了。更普遍的情况，可以开一棵线段树，预处理出每个节点从右往左合并的可持久化平衡树，直接把 \(O(\log n)\) 个区间的可持久化平衡树合并即可。
还有dsq的第二分块做法？好像是用 \(O(v)\) 复杂度合并一些值域然后值域分块。
Day 3
T1降智题写错，T2T3打暴力，再次垫底……
T1
sb题，降智题，nt题（指我自己）
\[\begin{aligned} &\oplus_{i=1}^n \oplus_{j=1}^i j[j|i]\\ =&\oplus_{j=1}^n j\oplus_{i=j}^n [j|i]\\ =&\oplus_{j=1}^n j(\lfloor\frac{n}{j}\rfloor \operatorname{and} 1) \end{aligned} \]直接整除分块搞就行了。
一定要注意，因为 \(2k \operatorname{xor} 2k+1=1\)，把左右的没有配对的处理掉之后，还需要看这个 \(1\) 的个数！
点击查看代码
#include
#include
#define rll register ll
using namespace std;
typedef long long ll;
ll n,ans;
int main(){
scanf("%lld",&n);
for(rll l=1,r;l<=n;l=r+1){
r=n/(n/l);
if(!((n/l)&1)) continue;
int len=r-l+1;
if(l&1) ans^=l,--len;
if(!(r&1)) ans^=r,--len;
if((len>>1)&1) ans^=1;
}
printf("%lld\n",ans);
return 0;
}
T2
两种做法，一种是平常的主席树或树套树优化建图跑tarjan，跑tarjan的时候就在主席树或者树套树上模拟那个过程就可以了。还有一种做法是考虑扫描的过程中有一个什么性质，然后可以直接做线段树分治。复杂度 \(1\) 到 \(2\) 个 \(\log\)。
T3
把点上的信息放到边上，然后对边维护连通块？具体好像是要开平衡树维护？？
Day 4
毒瘤场，T1读错题（虽然读对了也不会）所以爆零啦！
T1
\(O(n^3)\) 做法：把 \(a\) 和 \(b\) 都从小到大排序，考虑设 \(f_i\) 表示左边有 \(i\) 条边连上的方案数，\(g_i\) 表示右边有 \(i\) 条边连上的方案数，然后考虑枚举一个 \(i\) 作为中间点，左右两边各拿出 \(i\) 个点来匹配，贡献为 \(f_{L-i}\times g_{R-i}\times i!\)。求 \(f_i\) 和 \(g_i\) 大概就是设个 \(dp_{i,j}\)，由于限制越来越松很好转移。
code:(\(O(n^3)\))
点击查看代码
#include
#include
#include
#include
using namespace std;
const int N=300+13,mod=1e9+7;
int n,lena,lenb,a[N],b[N],A[N],B[N],L[N],R[N],f[N][N],mul[N];
inline void dpL(){
memset(f,0,sizeof f);
f[lena+1][0]=1;
for(int i=lena;i;--i){
int cnt=0;
for(int j=lenb;j;--j)
if(A[i]a[i]) B[++lenb]=b[j];
dpR();int r=lenb;int lim=min(l,r);
for(int j=0;j<=lim;++j) ans=(ans+1ll*L[l-j]*R[r-j]%mod*mul[j]%mod)%mod;
}
printf("%d\n",ans);
return 0;
}
\(O(n^2)\) 做法（srf） 考虑把 \(b\) 看成白点，\(a\) 看成黑点，都放到数轴上，题目中的限制条件就是前面的黑点和后面的白点不能都没匹配。设 \(dp_{i,j,0/1}\) 表示匹配到第 \(i\) 个点，后边的白点是不是必须匹配的方案数，不能套娃实际上就是合并线段之后不能有一段完全在另一段的前面。这个用 \(0/1\) 这一维就可以维护了。
T2
题意可以转化为找最多的斜率递增的向量 \((x_i,y_i)\) 首尾相连，使得满足 \(\sum x_i\leq n,\sum y_i\leq m\) 且 \(\frac{y_i}{x_i}\) 不同。
考虑直接跑一个暴力的背包，因为有 \(O(n,m)\) 个向量，所以复杂度是 \(O((nm)^2)\) 的。考虑剪枝，先把无用的向量去掉，比如 \(x_i\) 和 \(y_i\) 不互质和 \((x_i,y_i)\) 左下没有还没使用的线段。求一下大概发现有用的向量有 \(O(n^{\frac{2}{3}})\)，总复杂度 \(O(n^{\frac{11}{3}})\)。
然后继续剪枝背包的另外几维，最后可以优化到 \(O(n^{\frac{7}{3}})\)。
T3：P6107
建笛卡尔树之后考虑每一次操作相当于旋转？？六元环个数相当于是数四个三角形？？
Day 5
T1写了树套树套树……爆零了
T1
维护每个位置前面颜色和它相同的最近的位置 \(pre\)，修改操作只会修改 \(O(1)\) 个位置的 \(pre\)，查询操作直接线段树二分找 \(k\) 个 \(pre>s\) 的位置，由于最多只有 \(k\) 个颜色相同的，所以直接对于每个相同颜色找一下 \(\max\) 即可。
点击查看代码
#include
#include
#include
using namespace std;
typedef long long ll;
inline ll max(const ll&a,const ll&b){return a>b?a:b;}
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
void wt(ll x){if(x>9)wt(x/10);putchar(x%10+'0');}
const int N=2e5+13,logN=20;
set t[N];
set::iterator it;
int n,m,c[N],v[N],a[20],ppre[N];
namespace tree1{
struct SegTree{int l,r,maxpre;ll sum;}t[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((t[p].l+t[p].r)>>1)
inline void refresh(int p){
t[p].sum=t[ls].sum+t[rs].sum;
t[p].maxpre=max(t[ls].maxpre,t[rs].maxpre);
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r) return t[p].sum=v[l],t[p].maxpre=ppre[l],void();
build(ls,l,mid),build(rs,mid+1,r);
refresh(p);
}
void update(int p,int x,int y,int z){
if(t[p].l==t[p].r) return t[p].sum=y,t[p].maxpre=z,void();
x<=mid?update(ls,x,y,z):update(rs,x,y,z);
refresh(p);
}
ll query_sum(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r) return t[p].sum;
ll res=0;
if(l<=mid) res+=query_sum(ls,l,r);
if(r>mid) res+=query_sum(rs,l,r);
return res;
}
int getans(int p,int lim){
if(t[p].l==t[p].r) return t[p].l;
return t[ls].maxpre>=lim?getans(ls,lim):getans(rs,lim);
}
int find_right(int p,int l,int lim){
if(l<=t[p].l) return t[p].maxpre>=lim?getans(p,lim):0;
int res=0;
if(l<=mid) res=find_right(ls,l,lim);
if(res) return res;
return find_right(rs,l,lim);
}
#undef ls
#undef rs
#undef mid
}
namespace tree2{
int rt[N],tot;
struct SegTree{int ls,rs,maxx;}t[(N<<1)*logN];
#define ls t[p].ls
#define rs t[p].rs
#define mid ((l+r)>>1)
inline void refresh(int p){t[p].maxx=max(t[ls].maxx,t[rs].maxx);}
void update(int &p,int l,int r,int x,int v){
if(!p) p=++tot;
if(l==r) return t[p].maxx=v,void();
x<=mid?update(ls,l,mid,x,v):update(rs,mid+1,r,x,v);
refresh(p);
}
int query(int p,int l,int r,int x,int y){
if(!p) return 0;
if(x<=l&&r<=y) return t[p].maxx;
if(y<=mid) return query(ls,l,mid,x,y);
if(x>mid) return query(rs,mid+1,r,x,y);
return max(query(ls,l,mid,x,y),query(rs,mid+1,r,x,y));
}
#undef ls
#undef rs
#undef mid
}using tree2::rt;
int main(){
//freopen("gp.in","r",stdin);
//freopen("gp.out","w",stdout);
n=rd(),m=rd();
for(int i=1;i<=n;++i){
c[i]=rd(),v[i]=rd();
it=t[c[i]].end();
if(it!=t[c[i]].begin()) ppre[i]=*(--it);
tree2::update(rt[c[i]],1,n,i,v[i]);
t[c[i]].insert(i);
}
tree1::build(1,1,n);
while(m--){
int op,x,y,z,k;
op=rd(),x=rd();
if(op==1){
y=rd(),z=rd();
it=t[c[x]].upper_bound(x);
if(it!=t[c[x]].end()){
int nxt=*it,pre=0;
it=t[c[x]].lower_bound(x);
if(it!=t[c[x]].begin()) pre=*(--it);
tree1::update(1,nxt,v[nxt],ppre[nxt]=pre);
}
t[c[x]].erase(x);
tree2::update(rt[c[x]],1,n,x,0);
c[x]=y;
t[c[x]].insert(x);
it=t[c[x]].upper_bound(x);
if(it!=t[c[x]].end()){
int nxt=*it;
tree1::update(1,nxt,v[nxt],ppre[nxt]=x);
}
it=t[c[x]].lower_bound(x);int pre=0;
if(it!=t[c[x]].begin()) pre=*(--it);
tree1::update(1,x,v[x]=z,ppre[x]=pre);
tree2::update(rt[c[x]],1,n,x,v[x]);
}
else{
k=rd(),++k;int L=x,R=0;ll ans=0;
for(int i=1;i<=k;++i){
if(x<=n) a[i]=tree1::find_right(1,x,L);
if(!a[i]) a[i]=n+1;
if(x T2
先建出AC自动机，如果直接在上面跑消元，复杂度 \(O((nm)^3)\)。一种做法是由于它很稀疏，所以可以做稀疏矩阵高斯消元 \(O((nm)^2)\)。正解做法是考虑减少未知元的数量，因为 \(n\) 很小，所以trie树上的链很少，只有 \(n\) 条，对于链交的位置，设下面 \(|son|-1\) 条链为未知数，这样未知数的个数是 \(O(n)\)，可以通过。
还有一种做法是类似 [SDOI2017]硬币游戏的概率生成函数做法……
T3
压位高精直接做可以获得 \(30-50pts\)。正解做法是先把后面几步操作是什么预测出来，然后可以一起做。复杂度很玄学但是能过。
Day 6
T1想到了正解，最后一步本来可以二分或者三分的，结果 \(O(1)\) 求求错了……垫底了。
T1
考虑枚举中间交的那一部分，两边都是走最短路，这样有 \(O(n^2)\) 条路径。考虑当相交的距离相同的时候，最短的那个一定更优，所以只有 \(O(m)\) 条路径，每条路径相当于是一个二元组 \((a,b)\)，有 \(a\) 长度的相交路径和 \(b\) 长度的不相交路径。要分配 \(k\) 的话只需要三分一个最优值或者二分导数即可。
点击查看代码
#include
#include
#include
#include
#define re register
#define rint re int
#define rld re ld
using namespace std;
inline int rd(){
rint res=0;re char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
typedef long double ld;
inline int min(const int &a,const int &b){return aq;while(!q.empty())q.pop();
for(rint bgn=1;bgn<=n;++bgn){
memset(vis,0,sizeof vis);
q.push(bgn);dist[bgn][bgn]=0,vis[bgn]=1;
while(!q.empty()){
rint u=q.front();q.pop();
for(rint i=h[u];i;i=e[i].nxt){
rint v=e[i].v;if(vis[v]) continue;
q.push(v);vis[v]=1,dist[bgn][v]=dist[bgn][u]+1;
}
}
}
}
inline ld calc1(const int &k,const int &x){
if(!k) return x;
int p=k/x;int rest=k-p*x;++p;
return rest*((ld)1.0/(p+1))+(x-rest)*((ld)1.0/p);
}
inline ld calc2(const int &k,const int &x){
if(!k) return x*2;
int p=k/x;int rest=k-p*x;++p;
return rest*((ld)2.0/(p+1))+(x-rest)*((ld)2.0/p);
}
inline ld solve(const int &k,const int &x,const int &y){//y条重的，x条不重的
if(!y){
if(!x) return 0;
return calc1(k,x);
}
if(!x) return calc2(k,y);
int l=0,r=k;
while(l>1;
if(calc1(mid,x)+calc2(k-mid,y)>calc1(mid+1,x)+calc2(k-mid-1,y)) l=mid+1;
else r=mid;
}
return calc1(l,x)+calc2(k-l,y);
}
int main(){
/*freopen("20.in","r",stdin);
freopen("city.out","w",stdout);*/
n=rd(),m=rd(),K=rd();
for(rint i=1,u,v;i<=m;++i) u=rd(),v=rd(),add(u,v),add(v,u);
init();
s1=rd(),t1=rd(),s2=rd(),t2=rd();
memset(f,0x3f,sizeof f);
f[0]=dist[s1][t1]+dist[s2][t2];
for(rint i=1;i<=n;++i){
for(rint j=1;j<=n;++j){
if(dist[i][j]==INF||dist[i][s1]==INF||dist[j][t1]==INF) continue;
if(dist[i][s2]!=INF&&dist[j][t2]!=INF){
rint cnt=dist[i][j]+dist[i][s1]+dist[i][s2]+dist[j][t1]+dist[j][t2];
f[dist[i][j]]=min(f[dist[i][j]],cnt);
}
if(dist[i][t2]!=INF&&dist[j][s2]!=INF){
rint cnt=dist[i][j]+dist[i][s1]+dist[i][t2]+dist[j][t1]+dist[j][s2];
f[dist[i][j]]=min(f[dist[i][j]],cnt);
}
}
}
rld ans=0x3f3f3f3f;
for(int i=0;i<=m;++i)
if(f[i]!=INF){
rld res=solve(K,f[i]-i,i);
ans=min(ans,res);
}
printf("%.12Lf\n",ans);
return 0;
}
T2
不会啊……有一个做法好像是区间dp的把两维互换（因为答案显然比较小）。
T3
扫描线扫 \(x\) 维，相当于是每一次加入或删除一个“井”字形，维护这个图形的补集，也就是 \(4\) 个 2-side 矩形。后面的不会啦……
Day 7
T3口胡出做法完全写不出……T1没有仔细想……然后十点半心态崩了，最后暴力都没打垫底了。
T1
T2
T3
Day 8
T1
\(n+k-1-a(k-1)\choose k-1\)
T2
T3
Day 9
T1
T2
T3
Day 10
T1
T2
T3
讲课
Day 1
讲题：
T1 EC-Final G
给一个序列，每次查询一个区间的子区间中颜色数是奇数的个数。
相当于是颜色数 \(\mod 2\)。考虑右端点扫描线，左端点使用数据结构维护，大概是说进来之后要对一些东西异或 \(1\)，最后查一个区间历史和。线段树可以直接维护，复杂度 \(O((n+m)\log n)\)。
T2 Uoj神秘题
给一个序列，每次查询区间中出现偶数次的数的异或和。
异或的神秘性质，偶数次的数异或和等于区间异或和异或上出现奇数次的数的异或和。和上面那个题同样统计即可。
T3 JOISC2021 饮食区
\(n\) 个队列 \(m\) 次操作，每次加入 \(k\) 个 \(type=c\) 的人或者删掉 \(k\) 个人或者查询第 \(k\) 个人的 \(type\)。
离线，扫描线扫序列，数据结构维护时间，每次操作拆成两次单点。注意到 \(<0\) 时变成 \(=0\) 的操作不好维护，那就可以先去在线段树上二分找到离某一次操作最近的那次 \(<0\) 的位置，需要维护一个前缀和的 \(\min\)。
注意这题在线段树上二分是从右到左，先向上再向下。
T4 某经典问题
DAG上，每个点出发边权不同，每次查询从某个点出发字典序 \(kth\) 的路径到哪个点。\(n,m\leq 10^5,k\leq 10^{18}\)。
可持久化平衡树可以做到区间复制的指数级增长，DAG的路径数也是指数及增长。大概就是从后往前拓扑排序的过程中做区间复制然后把多余的删去即可。
T5 Luogu6617
记录一下每个点前面最近的加起来等于 \(w\) 的点，如果没有修改，相当于是区间取 \(\max\)，看看这个值是否 \(\geq l\)。带修改的话，如果很多个点的前驱都是一个点，改这个点的复杂度会炸。考虑如果有一个 \(x\) 指向 \(y(y
点击查看代码
#include
#include
#include
using namespace std;
inline int max(const int &a,const int &b){return a>b?a:b;}
inline int rd(){
int res=0;char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())res=(res<<1)+(res<<3)+(c-'0');
return res;
}
const int N=5e5+13;
int n,m,w,a[N],b[N],c[N];
set p[N];
set::iterator it;
struct SegTree{int l,r,maxx;}t[N<<2];
#define ls p<<1
#define rs p<<1|1
#define mid ((t[p].l+t[p].r)>>1)
inline void refresh(int p){t[p].maxx=max(t[ls].maxx,t[rs].maxx);}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r) return t[p].maxx=b[l],void();
build(ls,l,mid),build(rs,mid+1,r);
refresh(p);
}
void update(int p,int x,int k){
if(t[p].l==t[p].r) return t[p].maxx=k,void();
x<=mid?update(ls,x,k):update(rs,x,k);
refresh(p);
}
int query(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r) return t[p].maxx;
int res=0;
if(l<=mid) res=max(res,query(ls,l,r));
if(r>mid) res=max(res,query(rs,l,r));
return res;
}
#undef mid
int main(){
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
n=rd(),m=rd(),w=rd();
for(int i=1;i<=n;++i){
a[i]=rd();
it=p[w-a[i]].end();
if(it!=p[w-a[i]].begin()){
int pos=*(--it);
if(!c[pos]) b[i]=pos,c[pos]=i;
}
p[a[i]].insert(i);
}
build(1,1,n);
int las=0;
while(m--){
int op,x,y;
op=rd(),x=rd(),y=rd();
if(op==1){
if(c[x]){//处理指向x的那个位置 c[x]
it=p[a[x]].lower_bound(x);
if(it!=p[a[x]].begin()){//前面还有
int pre=*(--it);
if(!c[pre]) b[c[x]]=pre,c[pre]=c[x],update(1,c[x],pre);
else b[c[x]]=0,update(1,c[x],0);
}
else{//前面没了
b[c[x]]=0;
update(1,c[x],0);
}
c[x]=0;
}
it=p[a[x]].lower_bound(x);++it;
if(b[x]){//处理后面的位置连到x指到的位置
if(it!=p[a[x]].end()){
int nxt=*it;
if(b[nxt]x){
b[c[pre]]=0;
update(1,c[pre],0);
c[pre]=x,b[x]=pre;
update(1,x,pre);
}
}
}
else{
x^=las,y^=las;
int res=query(1,x,y);
if(res>=x) putchar('Y'),putchar('e'),putchar('s'),++las;
else putchar('N'),putchar('o');
putchar('\n');
}
}
return 0;
}
P.S.这题细节太多了！set 这东西真的全是细节！！建议改成【模板】set！！
T6 bzoj3489
可持久化树套堆？？？
T7 [Ynoi2007] rgxsxrs
值域分块？爬了爬了……
T8 Loj6276
一棵树，点有颜色，求有多少条链上的点颜色互不相同。每种颜色出现次数 \(\leq 20\)，\(n\leq 10^5,4s\)。
T9 Luogu7126
太困了，爬了爬了
T10 Uoj207
每一对点赋一个随机大整数，LCT维护子树异或和。一条边满足条件，相当于是这条边的某个端点子树内包含了所有点对中的某个点。
Day 2
CF464E
首先可以使用01-trie维护最短路数组，每一次三角不等式转移相当于都是做了一个复制再修改，可以使用可持久化数据结构维护。判断大小可以直接区间哈希LCP找到第一个不一样的位置，比大小即可。复杂度 \(O((n+m\log n)\log v)\)。
CF1446D2
加强：\(n\leq 5\times 10^7\)。