A 挤压
看到异或首先拆位，看到统计期望的次幂考虑二项式定理或者组合意义。发现二项式定理不会，然后思考平方式子拆开，\(s_i\) 表示 \(2^i\)，\(x^2=\sum_{i=1}s_i\sum_{j=1}s_j=\sum_{i=1}\sum_{j=1}s^{i+j}\)，然后设 \(f_{i,j,0/1,0/1}\) 表示到当前数异或之后，第 \(i\) 位为 \(0/1\)，第 \(j\) 位为 \(0/1\) 的概率，最终答案就是 \(\sum_{i=1}\sum_{j=1}f_{i,j,1,1}s^{i+j}\)，转移分讨即可。
B 工地难题
看到恰好，考虑容斥，计算 \(ans_i\) 表示连续不超过 \(i\) 的方案数，答案即为 \(ans_k-ans_{k-1}\)。
把 \(0\) 当成分割线，现在问题成了选出 \(n-m+1\) 个范围在 \([0,k]\) 的数，他们的和为 \(m\) 的方案数，减去不合法的方案就是答案，\(f_i\) 表示钦定了 \(i\) 个段不合法的方案，这些数有了下界，考虑把下界减去，就成了一般情况，方案数为 \(n-i(k+1)\choose n-m\)，然后考虑钦定的方案数，为 \(n-m+1\choose i\)，所以 \(f_i={n-m+1\choose i}{n-i(k+1)\choose n-m}\)，\(g_i\) 表示恰好有 \(i\) 个段不合法的方案数，有 \(f_i=\sum_{j=0}{j\choose i}g_j\)，\(g_0\) 就是答案，二项式反演得知 \(g_0=\sum_{i=0}^{n-m+1}(-1)^{i}f_i\)，有意义的 \(f_i\) 有 \(\frac{n-m}{k+1}\) 个，时间复杂度根据调和级数得出，为 \(\mathcal{O}(n\log n)\)。
C 星空遗迹
观察发现，两个相邻的只留一个即可，强的夹弱的只留强的即可，所以只有前面一直赢后面和后面一直赢前面两种情况了，这样一直赢的就是答案，因为它能赢的一直在帮它消除能赢它的。
考虑维护一个前面赢后面的栈，栈底就是胜者，如果当前能赢栈顶，弹栈，\(size\) 减小 \(1\)，如果一样，不操作，\(size\) 不变，如果输了，入栈，\(size\) 增加 \(1\)，特殊的，如果栈为空时需要把当前元素加入栈中，最后一个栈大小为 \(1\) 的位置就是栈底。其实，并不用去真正的维护一个栈，因为自始至终我们都知道栈顶的元素，对于位置 \(i\)，栈顶都是 \(s_i\)，首先如果它入栈了，栈顶是他，如果没有入栈，一种是和栈顶一样，一种是栈顶被弹出，新栈顶和它一样，所以每次只用比较 \(s_i\) 和 \(s_{i-1}\) 即可。
有了栈大小为 \(1\) 的限制很难做，考虑栈为空时不管，该减继续减，这样栈最小时的位置就是栈底，处理出每次入栈的变化值 \(f_i\)，\(i\) 位置栈的大小为 \(\sum_{j=1}^if_j\)，每次修改改变了 \(f_i\)，所以这是一个区间加，单点查最小值的过程，线段树维护即可。
#include<bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
#define eb emplace_back
#define fo(i,s,t) for(int i=s;i<=t;++i)
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e5+10;
struct GA{
char s;
friend bool operator>(GA a,GA b){
if(a.s==b.s)return true;
if(a.s=='P'&&b.s=='R')return true;
if(a.s=='R'&&b.s=='S')return true;
if(a.s=='S'&&b.s=='P')return true;
return false;
}
}a[N];
int n,q,si[N],f[N];
struct TREE{int min,tag,id;}t[N<<2];
inline void pushdown(int p){
t[ls].min+=t[p].tag,t[rs].min+=t[p].tag;
t[ls].tag+=t[p].tag,t[rs].tag+=t[p].tag;
t[p].tag=0;
}
inline void update(int p){
if(t[ls].min<t[rs].min){t[p]={t[ls].min,0,t[ls].id};}
else t[p]={t[rs].min,0,t[rs].id};
}
inline void change(int p,int l,int r,int pos,int x){
if(l>=pos){t[p].min+=x;t[p].tag+=x;return ;}
if(t[p].tag)pushdown(p);
int mid=l+r>>1;
if(pos<=mid)change(ls,l,mid,pos,x);
change(rs,mid+1,r,pos,x);
update(p);
}
inline void build(int p,int l,int r){
if(l==r){t[p]={si[l],0,l};return ;}
int mid=l+r>>1;
build(ls,l,mid);build(rs,mid+1,r);
update(p);
}
inline std::pair<int,int> query(int p,int l,int r,int L,int R){
if(l>=L&&r<=R)return {t[p].min,t[p].id};
std::pair<int,int> res;
int mid=l+r>>1,pd=0;
if(t[p].tag)pushdown(p);
if(L<=mid)pd=1,res=query(ls,l,mid,L,R);
if(R>mid){
auto it=query(rs,mid+1,r,L,R);
if(pd)res=std::min(res,it);
else res=it;
}
return res;
}
signed main(){
freopen("a.in","r",stdin);freopen("a.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read();q=read();for(int i=1;i<=n;++i){char ch=getchar();while(ch<'A'&&ch>'Z')ch=getchar();a[i]={ch};}
si[1]=1;f[1]=1;
for(int i=2;i<=n;++i){
si[i]=si[i-1];
if(a[i].s==a[i-1].s)continue;
if(a[i]>a[i-1])si[i]--,f[i]=-1;
if(a[i-1]>a[i])si[i]++,f[i]=1;
}
build(1,1,n);
while(q--){
int op=read();
if(op==1){
int k=read();char ch=getchar();
while(ch<'A'||ch>'Z')ch=getchar();
GA it={ch};int zc=0;
if(k!=1){
if(it>a[k-1])zc=-1;
if(a[k-1]>it)zc=1;
if(it.s==a[k-1].s)zc=0;
change(1,1,n,k,zc-f[k]);
f[k]=zc;
}
zc=0;
if(k!=n){
if(it>a[k+1])zc=1;
if(a[k+1]>it)zc=-1;
if(it.s==a[k+1].s)zc=0;
change(1,1,n,k+1,zc-f[k+1]);
f[k+1]=zc;
}
a[k]=it;
}else{
int l=read(),r=read();
std::cout<<a[query(1,1,n,l,r).second].s<<'\n';
}
}
}
D 纽带
不会
标签：ch,return,int,sum,40,zc,read,CSP,模拟 From： https://www.cnblogs.com/Ishar-zdl/p/18453070