我疯了，所以现在我做一道题记一道题。
T1 西鸹喝水
意外地很快做出来了。
用到了异或和和前缀和的结合，这个题就很神奇地想到了。首先这种区间的可以拿序列分治，但一般我是想不到的。还有就是类似每个区间的最值和的题，拿栈（单调栈）做的，洛谷有道题的，忘了题号了。
这个题就先给 \(k\) 分解因数，这个均摊大概是 \(\log\)，上界大概是 \(2\sqrt{k}\)，大概能卡过吧(
记住前缀和，发现对于每个边界 \(r\)，要找的就是有几个 \(l\) 满足 \(r\) 的前缀和异或上 \(l\) 的前缀和是 \(k\) 的因数。等式基本性质就拿 \(r\) 点的前缀和异或上每个因数，找满足条件的 \(l\) 嘛，拿桶维护这一过程，扫一遍。
T2 小清新人渣的本愿
bitset好题。一开始没明白tag里的“枚举”是什么意思，看了题解，好吧明白了（
这个题按说真不难，就是对我来说维护和卡常的方式很巧妙。看到这个题莫队大概确实是第一选项吧(
维护：熟练运用了等式的基本性质和换元。首先肯定要维护个桶吧；对于减的操作，发现如果有 \(a-b==x\) 则有 \(a==b+x\)，所以如果 \(b\) 和 \(b+x\) 两个数在区间都存在；对于乘的操作，发现给 \(x\) 枚举因数复杂度最多也就 \(O(n\sqrt{n})\)，没有问题。这个加的操作就很巧妙，比较直接的思路大概会 \(a==x-b\)，但这个时候是会有负数的，如果你想带个 \(\log\) 可能会用 \(map\)，这里是用了换元，设 \(b'=maxn-b\)(\(maxn\) 这里同时也是值域最大值，目的是绕开负数) 就有 \(a-b'=a+b-maxn=x-maxn\)，即 \(b'=a+(maxn-x)\) 的时候成立，只要这个 \(a\) 和 \(b'\) 存在就行，我们直接再开个桶来维护 \(maxn-a\) 存在哪些值就好了。
卡常：我觉得这其实超出卡常范畴了，这是直接拿bitset降低了复杂度了。首先bitset的位运算复杂度是 \(O(\dfrac{len}{w})\)，这个 \(len\) 为其长度，\(w\) 为“计算机中把 \(w\) 位看作一个整型长度”，咱们看游戏配置的时候的32位和64位就是这个意思。这里用bitset的原因是，如果用了普通的数组维护桶，那么看和每个数有没有和它关系满足能满足操作条件的数就要用循环，枚举值域，复杂度 \(O(nm)\)；但是拿bitset可以直接用位运算，值的加减拿位移代替，检验是不是这个数和加减完的数都在区间存在用与运算，检验与出来是不是0用bitset自带函数any()，返回这个数是不是非零。下来复杂度 \(O(\dfrac{nm}{64})\)。三秒，这个其实跑得很快，是完全可以过的(
T3 弹珠
水题。图的连通性。拿背包看看总值一半的值拼不拼得出来就好了。这个直接过不去，有个hack点，拿bitset玄学优化就好了。
T4 草莓列车
最好的草莓列车肯定在1A凹吧(毕竟有俩金(
这个赛时打了个60pts线段树，和20pts特殊性质。线段树赛后卡过去了(
线段树大概最好复杂度是 \(O(m\log n)\)，应该是不对的。这个题数据造的惊为天人，如果 \(m>2e5\)，直接让 \(m=2e5\)，只处理这些询问，答案一样(
赛时的第一思路是扫描线，想个什么办法比较快地确定最大值突然没有之后的新的最大值。一开始认为 \(v\le 1e5\) 的时候想的是权值线段树和二分，复杂度 \(O(n\log ^2 n)\) 。但是第二个样例 \(v\) 就大于1e5了，显然它寄了。
后来就是想得打标记，直接把修改的值按大小排序，那么修改就直接在线段树上修改就好。后来发现不用排序，修改的时候稍微比较一下能达到一样的效果。
写线段树之前想到，我们只是相当于给一些区间打标记，没必要拿线段树这种修改的做。拿了线段树就除了叶子那层，其他都在浪费。
当时没想到拿倍增打标记。
好吧，拿st表那个思路，倒着来，一个区间就分成两个小区间分别打，然后这是 \(O(1)\) 的，相当于每个区间内部的值至少是这个st表数组这么大。因为整个st表的数组哪些有值不好确定，所以咱直接对于每个数下放，和st表预处理正好相反，拿大区间值赋给小区间。
最后到0次，输出直接和原值比较就好了。
T5 青鸹
规律题。需要非常地发散。
发现要是想把两个数的值合并，这两个数一定相隔奇数个数，换句话说这两个数的下标的奇偶性相同。
也就确定了最大值就是奇数位置上的正数之和和偶数位置上的正数之和的最大值。
然后看看怎么消不想要的数。每次去掉你不想要的长度的数，需要长度除以2加一次。做就行了
T6 森林
太痛苦了天天快乐
细节很多的主席树好题。
首先想这个合并，做法是直接启发式嗯并，每次扫一遍较小的树，这个复杂度是对的。因为对于一个连通块，大小为 \(size\)，它如果被扫了，那么它的 \(size\) 至少增加为原本的二倍（显然
然后最初所有块的大小都是1，最坏情况下，所有的块都一路乘以2并起来，为 \(\log \dfrac{n}{size==1}\)。肯定跑不满。所以总的复杂度就是 \(O(n\log^2 n)\)，能过。
因为合并最多一个点 \(\log n\) 次，乘上主席树原本的 \(\log n\)，开 \(\log^2 n\) 倍的maxn就好。看题解开了600倍，感觉没啥必要。
树上的主席树，也挺简单。维护的时候直接维护从根节点到目标处的值，然后查的时候拿 \(x\) 和 \(y\) 的信息减去 \(lca_{x,y}\) 和 lca他爹 的信息就好，就是多几个参的区间第 \(k\) 大。
这里的 \(x\) 和 \(y\) 不能相等，原因是：在我的写法里，如果关于 \(x\) 或者 \(y\) 都没有被插入过，那么这个点就是不存在的。不存在就全是0，只能查出0来。
对于这个问题加个特判就行，也可以每次查询看看当前查询节点存不存在，不存在就空插一个节点。因为有过合并的节点前面合并时候已经查看过了，一定存在，所以事实上会不存在，再插入的节点一定是单个节点，所以没啥问题。
这个我想放个代码
#include<bits/stdc++.h>
typedef int count ;
typedef long long value ;
inline value read(){
count f(1);
value x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
void write(value x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
#define debug(x) std::cerr<<"###"<<x<<std::endl;
#define maxn 80010
count firewatch;
count n,m,q;
value a[maxn],real[maxn];
value book[maxn];
count cnt;
count head[maxn],tot=1;
struct bian{
count to,nx;
} bian[maxn<<1];
inline void add(count from,count to){
bian[++tot].to=to;
bian[tot].nx=head[from];
head[from]=tot;
}
count father[maxn];
inline count find(count x){
if(father[x]!=x) father[x]=find(father[x]);
return father[x];
}
count size[maxn],dep[maxn];
count f[20][maxn];
inline count lca(count x,count y){
if(dep[x]>dep[y]) std::swap(x,y);
for(count i=17;i>=0;i--){
if(dep[x]<=dep[f[i][y]]){
y=f[i][y];
}
}
if(x==y) return x;
for(count i=17;i>=0;i--){
if(f[i][x]!=f[i][y]){
x=f[i][x];
y=f[i][y];
}
}
return f[0][x];
}
count rt[maxn],all;
struct tree{
count l,r;
count ls,rs;
value cnt;
} shu[maxn*257];
inline void copy(count &hao){
shu[++all]=shu[hao];
hao=all;
}
inline void pushup(count hao){
shu[hao].cnt=shu[shu[hao].ls].cnt+shu[shu[hao].rs].cnt;
}
void insert(count &hao,count l,count r,count x){
copy(hao);
shu[hao].l=l,shu[hao].r=r;
if(l==r){
shu[hao].cnt++;
return ;
}
count mid=(l+r)>>1;
if(x<=mid) insert(shu[hao].ls,l,mid,x);
else insert(shu[hao].rs,mid+1,r,x);
pushup(hao);
}
count ask(count hao1,count hao2,count hao3,count hao4,count k){
// debug(hao1<<' '<<hao2<<' '<<hao3<<' '<<hao4)
if(shu[hao1].l==shu[hao1].r && shu[hao2].l==shu[hao2].r){
// debug(k<<' '<<std::max(shu[hao1].l,shu[hao2].l));
return std::max(shu[hao1].l,shu[hao2].l);
}
// assert(shu[0].cnt == 0);
count x=shu[shu[hao1].ls].cnt+shu[shu[hao2].ls].cnt-shu[shu[hao3].ls].cnt-shu[shu[hao4].ls].cnt;
// debug(k<<' '<<x)
if(x>=k){
return ask(shu[hao1].ls,shu[hao2].ls,shu[hao3].ls,shu[hao4].ls,k);
} else{
return ask(shu[hao1].rs,shu[hao2].rs,shu[hao3].rs,shu[hao4].rs,k-x);
}
}
void dfs(count x,count fa,count gen){
f[0][x]=fa;
for(count j=1;j<=17;j++){
f[j][x]=f[j-1][f[j-1][x]];
}
rt[x]=rt[fa];
insert(rt[x],1ll,cnt,real[x]);
size[gen]++;
dep[x]=dep[fa]+1;
for(count i=head[x];i;i=bian[i].nx){
count y=bian[i].to;
if(y==fa) continue;
dfs(y,x,gen);
}
}
int main(){
// freopen("P3302_2.in","r",stdin);
// freopen("P3302.out","w",stdout);
firewatch=read();
n=read(),m=read(),q=read();
for(count i=1;i<=n;i++){
a[i]=read();
book[i]=a[i];
}
std::sort(book+1,book+1+n);
cnt=std::unique(book+1,book+1+n)-book-1;
for(count i=1;i<=n;i++){
real[i]=std::lower_bound(book+1,book+1+cnt,a[i])-book;
}
for(count i=1;i<=n;i++){
father[i]=i;
size[i]=1;
dep[i]=1;
}
for(count i=1;i<=m;i++){
count b=read(),c=read();
add(b,c);
add(c,b);
count x=find(b);
count y=find(c);
if(size[x]>size[y]){
if(!rt[x]){
insert(rt[x],1ll,cnt,real[x]);
}
dfs(c,b,x);
father[c]=father[y]=x;
} else{
if(!rt[y]){
insert(rt[y],1ll,cnt,real[y]);
}
dfs(b,c,y);
father[b]=father[x]=y;
}
}
value lst=0;
while(q--){
char ch;
std::cin>>ch;
if(ch=='L'){
value b=read(),c=read();
b^=lst,c^=lst;
add(b,c);
add(c,b);
count x=find(b),y=find(c);
if(size[x]>size[y]){
if(!rt[x]){
insert(rt[x],1ll,cnt,real[x]);
}
dfs(c,b,x);
father[y]=father[c]=x;
} else{
if(!rt[y]){
insert(rt[y],1,cnt,real[y]);
}
dfs(b,c,y);
father[x]=father[b]=y;
}
} else{
value x=read(),y=read(),k=read();
x^=lst,y^=lst,k^=lst;
count an=lca(x,y);
count fan=f[0][an];
if(!rt[x]){
insert(rt[x],1ll,cnt,real[x]);
}
if(!rt[y]){
insert(rt[y],1,cnt,real[y]);
}
lst=book[ask(rt[x],rt[y],rt[an],rt[fan],k)];
write(lst),putchar('\n');
}
}
return 0;
}
T7 count on a tree
和T6双倍经验。没有在线的连边。
这个没必要那么麻烦了，直接树链剖分求lca然后直接树上主席树就好了，比这个做法少一个 \(\log\)。
我是又打了一遍(
T8 暴力操作
加了维护m+1的c，删了个赛时的地方，很神奇地过了。我觉得大概好像也没什么问题但是这个过了就很不可思议。
首先肯定只处理前半部分。
感谢CCComfy答疑解惑：这玩意儿存不存在压根不单调。
能对的原因是每次如果不存在一个枚举的 \(mid\)，一定有剩下的数都比枚举的 \(mid\) 都小，肯定有更优。
此外思路没啥难的，感觉比较容易想到二分。每次就检验把其他会影响中位数取值的数删成比较小的数，然后看看花费合不合法。因为有 \(\lfloor \dfrac{a_i}{x} \rfloor \le mid\)，能得出 \(a_i<(mid+1)x\)，就有 \(x>\dfrac{a_i}{mid+1}\)，可以 \(O(1)\) 得出 \(x=\lfloor\dfrac{a_i}{mid+1}\rfloor+1\)（即该除以的倍数
然后一个细节，就是把一些数删成0的时候就可能会有那种超出 \(m\) 的除法，就直接把它们归类到第 \(m+1\) 的位置就好了（根据上面式子可得）。
代码
#include<bits/stdc++.h>
typedef int count ;
typedef long long value ;
inline value read(){
count f(1);
value x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
void write(value x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
#define debug(x) std::cerr<<"###"<<x<<std::endl;
#define shj(x) std::cerr<<1.0*clock()/CLOCKS_PER_SEC<<std::endl;
#define maxn 500010
count n,m,jie;
value k;
value a[maxn],c[maxn],cun[maxn];
bool check(value mid){
value val=0;
for(count i=1;i<=jie;i++){
value ned=(a[i]/(mid+1))+1;
val+=c[ned];
a[i]/=ned;
}
if(val>k) {
return 0;
}
//以下就是询问的部分，删掉能对，不删就错
// bool flag=0;
// for(count i=1;i<=jie;i++){
// if(a[i]==mid){
// flag=1;
// break;
// }
// }
// if(!flag) {
// return 0;
// }
return 1;
}
int main(){
freopen("opt.in","r",stdin);
freopen("opt.out","w",stdout);
n=read(),m=read(),k=read();
for(count i=1;i<=n;i++){
a[i]=read();
cun[i]=a[i];
}
for(count i=1;i<=m;i++){
c[i]=read();
for(count j=2;j<=sqrt(i);j++){
if(i%j) continue;
c[i]=std::min(c[i],c[j]+c[i/j]);
}
}
count xiao=m;
for(count i=m-1;i>=1;i--){
if(c[i]<c[xiao]) xiao=i;
c[i]=c[xiao];
}
c[1]=0;
c[m+1]=INT_MAX;
count now=(m+1)/2+((m+1)%2!=0);
for(count i=2;i<=n;i++){
while((now-1)*i>=m+1){
now--;
}
c[m+1]=std::min(c[m+1],c[now]+c[i]);
}
xiao=m+1;
for(count i=m;i>=1;i--){
if(c[i]<c[xiao]) xiao=i;
c[i]=c[xiao];
}
std::sort(a+1,a+1+n);
std::sort(cun+1,cun+1+n);
jie=(n>>1)+1;
count l=0,r=a[jie];
while(l<r){
value mid=(l+r)>>1;
if(check(mid)){
r=mid;
} else{
l=mid+1;
}
for(count i=1;i<=jie;i++){
a[i]=cun[i];
}
}
write((l+r)>>1),putchar('\n');
return 0;
}
T9 种树
Sonnety倾情推荐“要是你跟出题人脑筋撞上（FLORIZ：好恐怖的修辞手法）就很简单”。
我是没对上，所以我看了题解(
比较能看出来，每个数的因数就是 \(\prod_{d|p_i,d is prime} d\)
考虑对 \(w\) 的某个质因数单独考虑，设 \(a_i\) 就是 \(p_i\) 里面这个因数的次数，每次乘上这个数就是给 \(a_i\) +1。
然后就比较直接了，把每个质因数对应的 \(a\) 序列里面的最小的 \(a_i\) 次数+1。根据什么什么正方形的面积什么什么，这样显然更好。
复杂度很神秘 \(O(n\log n \sqrt{n})\)。
T10 flandre
写挂了。
首先选的所有数一定是递增排列的。正数是必选的。
排好序了。从负数第一个开始倒着扫，统计每个数之后选了多少数，如果这个数量*\(k\)+这个负数>=0，必选。
细节是一定要给空位置（值为0）初始化(
怕我自己都不知道是啥意思放个code吧(
#include<bits/stdc++.h>
typedef int count ;
typedef __int128 value ;
inline value read(){
count f(1);
value x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
void write(value x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
#define debug(x) std::cerr<<"###"<<x<<std::endl;
#define maxn 1000010
count n;
value k;
value xu[maxn];
count cnt;
value ans;
bool yes[maxn];
struct hao{
count ha;
value val;
bool friend operator < (const hao& x,const hao& y){
return x.val<y.val;
}
} a[maxn];
int main(){
// freopen("flandre.in","r",stdin);
freopen("flandre.in","r",stdin);
freopen("flandre.out","w",stdout);
n=read(),k=read();
for(count i=1;i<=n;i++){
a[i].val=read();
a[i].ha=i;
}
std::sort(a+1,a+1+n);
count jie=0;
for(count i=0;i<=n;i++){
if(i<n && a[i+1].val>0){
jie=i;
break;
}
}
// debug(jie)
if(!jie) jie=n;
value now=n-jie;
for(count i=jie;i>=1;i--){
if(a[i].val+k*now>=0){
yes[i]=1;
now++;
}
}
for(count i=jie+1;i<=n;i++){
yes[i]=1;
}
// debug("ok")
value tong=1,pre=0;
a[0].val=1e7;
for(count i=1;i<=n;i++){
if(yes[i]){
xu[++cnt]=a[i].ha;
tong++;
if(a[i].val!=a[pre].val) tong=1;
ans+=k*(cnt-tong)+a[i].val;
pre=i;
}
}
write(ans),putchar(' '),write(cnt),putchar('\n');
for(count i=1;i<=cnt;i++){
write(xu[i]),putchar(' ');
}
return 0;
}
T11 meirin
特别鸣谢 Sonnety 的细心讲解，FLORIZ这个B快不会做题了
推式子(
因为 \(a\) 是不会变的，考虑只对 \(a\) 进行前缀和或者前缀和的前缀和什么的。
这第一步就挺巧妙，考虑意义。每个 \(b_i\) 只会和满足 \(l\le i \&\& r\ge i\) 的 \(j\in[l,r]\) 的 \(a_j\) 相乘然后求和，这里是直接枚举的满足条件的 \(l,r\) 和其中的 \(i\)
(\(sum\) 是 \(a\) 的前缀和，\(sum'\) 是 \(sum\) 的前缀和)
原式\(=\Sigma_{x=1}^{n} (b_x \times \Sigma^{x}_{l=1}\Sigma_{r=x}^{n}\Sigma_{i=l}^{r})a_i\)
\(=\Sigma_{x=1}^{n} (b_x \times \Sigma^{x}_{l=1}\Sigma_{r=x}^{n}(sum_r-sum_{l-1}))\)
然后我们发现在第三层 \(\Sigma\) 里面这个 \(sum_{l-1}\) 在 \(x\) 不变的时候它的求和是可以直接算的，是 \(sum_{l-1}\times (n-x+1)\)
然后对于每个变化的 \(r\) 求的和，也是可以直接算的 \(sum'_n-sum'_{x-1}\)。
用类似的道理还能把第二层 \(\Sigma\) 也消了
\(=\Sigma_{x=1}^{n} (b_x \times \Sigma^{x}_{l=1} ((sum'_n-sum'_{x-1})-sum_{l-1}(n-x+1))\)
\(=\Sigma_{x=1}^{n} (b_x \times ((sum'_n-sum'_{x-1})x-sum'_{x-1}(n-x+1))\)
\(=\Sigma_{x=1}^{n} (b_x \times (x \times sum'_n-sum'_{x-1}(n+1))\)
然后就可以直接做了(
修改拿 \(b_x\) 后面这一大项前缀和修改就好。
T12 sakuya
啊啊啊啊啊赛时寄了
挺简单一个题，就是求特殊房间全排列的每两个相邻的点的距离之和的平均数
这个可以按每条边走到几次考虑。
比较直接可以考虑该子树内的特殊点个数和之外的特殊点个数。设这两个点相邻，然后发现这两个点有 \(m-1\) 种位置可能，每种位置可能的序列有 \((m-2)!\) 种可能，也就是还得乘上 \((m-1)!\)。
（题解好像用了更神奇的做法，不过我不知道）
然后统计每个点的相连边的经过的总数 \(f_x\)，修改就加上 \(f_x\times k\) 就好了
别忘了最后输出平均数的时候要乘上2，因为边是双向的。
T13 镜的绮想
sb卡常。double的map极慢，建议不用。
\(n^2\) 扫一遍，整一个桶，扫完统计桶的最大。
标签：count,rt,ch,shu,记录,最终,value,sum,刷题 From： https://www.cnblogs.com/eldenlord/p/17837119.html