Codecraft-20

CodeCraft-20 (Div. 2)

CF1316B String Modification

请先思考后再展开

把前k-1个看做整体,发现就是不断把最后那个人拉过去

因此最后是「k到n」+「前k-1个的正或反」

CF1316C Primitive Primes

请先思考后再展开

dif=1700,不会做,很棒

找到各自第一个$a_x和b_y \%p \ne 0,而i+j=x+y的每一对ij,一定有i<x或j<y,从而模出来是0$

确实是很妙的idea

CF1316D Nash Matrix

请先思考后再展开

将相同的看做一个块,普通的直接外向生成树就好了(且同种必须全部连通),关键是-1那些

发现可以随便找个两个相邻位置,建环大小为2的基环树即可,code

CF1316E Team Building

sb题,没啥好说的

CF1316F Battalion Strength

题意:定义序列p的权值为$\sum_i p_{a_i}*p_{a_i+1},a为排序排列,即p_{a_i} \le p_{a_{i+1}}$,q次单点修改,第一次前和每次修改后,输出随机选一个子序列,其权值的期望,$n \le 3e5$

请先思考后再展开

维护有序多重集,就是维护$\sum_{i<j} p_ip_j * 2^{-(j-i+1)}$,如果只做一次你可能会想写成$\sum p_i (\sum_{i<j} ..)$,但这样不好处理修改

众所周知很多单点修改的题目,可以考虑转化题意为可并信息(无脑的就是矩乘,有的就是自己定义两个结构体的运算),然后用线段树维护

对于本题而言,可以考虑将一段值域区间$[l,r]$的信息记录为:$(S,c,A=\sum_{i=1}^c p_i2^{i-1},B=\sum_{i=1}^c p_i2^{-i} )$,合并方法很明显了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int a[N],m;vc<int> nums;int find(int i){return lower_bound(all(nums),i)-nums.begin()+1;}
ll Bin[N],iBin[N];
namespace SGT
{
#define lc x<<1
#define rc x<<1|1
#define mid (l+r)/2
struct Data{ int S,A,B;int c; }dd[N<<2];
Data operator + (Data a,Data b){return {(a.S+b.S+a.A*iBin[a.c]%MOD*b.B)%MOD,(a.A+b.A*Bin[a.c])%MOD,(a.B+b.B*iBin[a.c])%MOD,a.c+b.c};}
void insert(Data &t,int p){ t.c++,add(t.S,t.A*iBin[t.c]%MOD*p%MOD),add(t.A,p*Bin[t.c-1]%MOD),add(t.B,p*iBin[t.c]%MOD); }
void erase (Data &t,int p){ add(t.A,MOD-p*Bin[t.c-1]%MOD),add(t.B,MOD-p*iBin[t.c]%MOD),add(t.S,MOD-t.A*iBin[t.c]%MOD*p%MOD),t.c--; }
void ch(int pos,int c,int x=1,int l=1,int r=m)
{
if(l==r){ assert(l==pos);if(c>0) insert(dd[x],nums[pos-1]); else erase(dd[x],nums[pos-1]);return; }
if(pos<=mid) ch(pos,c,lc,l,mid); else ch(pos,c,rc,mid+1,r);dd[x]=dd[lc]+dd[rc];
}
};
pii qes[N];
void main()
{
Bin[0]=iBin[0]=1;fo(i,1,N-1) Bin[i]=Bin[i-1]*2%MOD,iBin[i]=iBin[i-1]*((MOD+1)/2)%MOD;
int n=qread();fo(i,1,n) nums.PB(a[i]=qread());
int q=qread();fo(i,1,q) qes[i].FR=qread(),nums.PB(qes[i].SE=qread());
sort(all(nums));m=sz(nums);
fo(i,1,n) SGT::ch(a[i]=find(a[i]),1);fo(i,1,q) qes[i].SE=find(qes[i].SE);write2(SGT::dd[1].S);
fo(t,1,q) { int i=qes[t].FR,x=qes[t].SE;SGT::ch(a[i],-1),a[i]=x,SGT::ch(a[i],1);write2(SGT::dd[1].S); }
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/ded41f9d.html
转载请注明出处,谢谢!