0709

pair求最大的第一关键字小于等于x的对的要用：

it=st.lower_bound({x+1,0});
it--;

不能用：

it=st.upper_bound({x,0});
it--;

100pts->30pts

痛失 70pts 以及 3.5h

---

0710

并查集合并左右两个区间一定要维护区间左右端点。 以及一定要判 siz 大小（小的并到大的上）！

错误写法：

int merge(int x,int y){
	R[x]=R[y];
	cnt0[x]+=cnt0[y];
	cnt1[x]+=cnt1[y];
	while(!q[y].empty()) q[x].push(q[y].top()),q[y].pop();
	fa[y]=x;
	return x;
}

while(L[pos]<=h) pos=merge(find(pos-1),pos);
while(R[pos]<=h) pos=merge(pos,find(pos+1));

正确写法：

int merge1(int x,int y){
	R[x]=R[y],r[x]=r[y];
	cnt0[x]+=cnt0[y];
	cnt1[x]+=cnt1[y];
	while(!q[y].empty()) q[x].push(q[y].top()),q[y].pop();
	fa[y]=x;
	return x;
}
int merge2(int x,int y){
	L[y]=L[x],l[y]=l[x];
	cnt0[y]+=cnt0[x];
	cnt1[y]+=cnt1[x];
	while(!q[x].empty()) q[y].push(q[x].top()),q[x].pop();
	fa[x]=y;
	return y;
}
int merge(int x,int y){
	if(q[y].size()<q[x].size()) return merge1(x,y);
	else return merge2(x,y);
}

while(L[pos]<=h) pos=merge(find(l[pos]-1),pos);
while(R[pos]<=h) pos=merge(pos,find(r[pos]+1));

考场上耗费 20 min 调试。

---

0711

考场上看到体积一定价值单调递减要考虑有没有决策单调性！！考虑分治！！

背包转移考虑可不可以按 mod 一个数的余数分类！！！

---

0713

给出一个长度为 $N$，只含有大写字母 $A$ 和 $B$ 的字符串 $S=S_1S_2\dots S_n$，定义如下函数 $f(L,R,A,B)$：

function f(L, R, A, B):
   FOR i from L to R
       if S[i] = 'A'
           A = A + B
       else
           B = A + B
   return (A, B)

给出初始字符串，你需要执行以下次操作：

1 L R：将 $S_L,S_{L+1}\dots S_{R-1},S_R$ 取反（$A$ 变为 $B$，$B$ 变为 $A$）。

2 L R A B：输出函数调用的结果，对 $10^9+7$ 取模。

$1\le N,Q\le 10^5$

很明显是一道线段树维护矩阵的题，但是感觉操作一打 tag 时候的系数翻转很妙但是不会证（其实维护两个矩阵就不会有这样的问题但是懒hh）

void tag(){
	tg^=1;
	swap(A.a[1][2],A.a[2][1]);
	swap(A.a[1][1],A.a[2][2]);
}

大概是按矩阵旋转 180° 来证？并没有学会，待补。

其他操作就很套路了不提了。

---

0714

是否存在一个长度为 $n$ 的排列，使得其前缀积在 $\mod n$ 意义下两两不同？ $n \le 10^5$

首先当 $n$ 不为 4 且不是质数时无解，这个显然。

然后有个很神奇的结论就是我们可以构造出 $\forall i\in [1,n]$ 前 $i$ 个数的前缀积 $\mod n$ 余 $i$。

然后每个数 $a_i=i\times inv_{i-1}$（$inv_{i}$ 是 $i$ 在 $\mod n$ 意义下的逆元，因为 $n$ 是质数所以一定存在逆元），$a_1=1$。

然后因为是一个排列我们还要证明 $a_i$ 互不相等，简单拆一下式子：

$$a_i=i\times inv_{i-1}\\ =[(i-1)+1]\times inv_{i-1}\\ =(i-1)\times inv_{i-1}+inv_{i-1}\\ =1+inv_{i-1}\\ $$

因为 $i$ 不相等所以显然 $inv_{i-1}$ 不相等，证毕。

代码没什么好说的，注意特判 4 的情况即可。

#include<bits/stdc++.h>
#define FL(i,a,b) for(ll i=(a);i<=(b);i++)
#define FR(i,a,b) for(ll i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const ll MAXN = 1e5 + 10;
ll n;
ll ans[MAXN]; 
ll qpow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res=res*a%n;
		a=a*a%n;
		b>>=1;
	}
	return res;
}
signed main(){
	scanf("%lld",&n);
	if(n==4) printf("YES\n1\n3\n2\n4\n"),exit(0); 
	for(ll i=2;i*i<=n;i++)
		if(!(n%i)) puts("NO"),exit(0); 
	puts("YES");
	ans[1]=1;
	FL(i,2,n) ans[i]=i*qpow(i-1,n-2)%n,ans[i]=(!ans[i]?n:ans[i]);
	FL(i,1,n) printf("%lld\n",ans[i]);
}