B 选择题(DP 期望 退背包)

题目链接

第\(x\)个人的期望得分为：

\(cx\)表示\(x\)选了哪个选项，\(p(x,mx,cx)\)表示在\(cnt(mx)>\lfloor\frac n2\rfloor\)时，\(x\)选了\(cx\)的概率。
那么对\(cx\)分类讨论，\(f(x,mx,cnt)\)表示除\(x\)外，恰好有\(cnt\)个人选了\(mx\)的概率。则有

\(f(x,mx,cnt)\)的转移就是个背包。枚举\(x\)，就可以\(O(n^3)\)了。期望得分\(55\)。
我们发现\(x\)变成\(x+1\)时，对\(f\)的影响时，加入一个元素\(x\)并删掉\(x+1\)的影响。先拿所有人算一遍\(f\)，加入一个人就是做一遍\(O(n)\)的DP。把\(f\)的转移反过来就可以\(O(n)\)删掉\(x\)的贡献了：

\(j\)为\(0\)的时候特判。注意\(p\)为\(1\)的时候也要特判。
复杂度\(O(n^2)\)。

//226ms	536KB
#include 
#include 
#include 
#include 
#define gc() getchar()
#define mod 998244353
#define Mod(x) x>=mod&&(x-=mod)
typedef long long LL;
const int N=2005;

int P[N][4],W[4][4],f[N],g[N];
LL Ans[N];

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
inline int Inv(int x,int k=mod-2)
{
	int t=1;
	for(; k; k>>=1,x=1ll*x*x%mod)
		if(k&1) t=1ll*t*x%mod;
	return t;
}
void Solve(int n,int mx)
{
	memset(f,0,sizeof f);
	f[0]=1;
	for(int i=1; i<=n; ++i)
	{
		LL p=P[i][mx];
		for(int j=i; j; --j)
			f[j]=p*f[j-1]%mod+(1-p)*f[j]%mod, Mod(f[j]);//就是(mod+)1-p啊（mod-p是-p）
		f[0]=(1-p)*f[0]%mod;
	}
	for(int i=1; i<=n; ++i)//x
	{
		LL p=P[i][mx];
		if(p!=1)
		{
			LL inv=Inv(mod+1-p);
			g[0]=inv*f[0]%mod;
			for(int j=1; j<=n; ++j) g[j]=inv*(f[j]-p*g[j-1]%mod)%mod;
		}
		else
		{
			for(int j=0; j>1)+1; j<=n; ++j) tmp+=g[j];
		tmp%=mod;
		for(int j=0; j<4; ++j) Ans[i]+=1ll*W[mx][j]*P[i][j]%mod*(tmp+(mx==j?g[n>>1]:0))%mod;//cx
	}
}

int main()
{
	int n=read();
	for(int i=1; i<=n; ++i)
		P[i][0]=read(),P[i][1]=read(),P[i][2]=read(),P[i][3]=read();
	for(int i=0; i<4; ++i)
		W[i][0]=read(),W[i][1]=read(),W[i][2]=read(),W[i][3]=read();
	for(int mx=0; mx<4; ++mx) Solve(n,mx);
	for(int i=1; i<=n; ++i) printf("%d\n",(int)((Ans[i]%mod+mod)%mod));

	return 0;
}

C 树(树链剖分)

题目链接

是不是写出这题，树剖就无敌了啊。。
写完啦！感觉还好，也就6k嘛。

肯定要用点来表示边的颜色，然后树剖。
对于操作2，我们可以拆成：
1.将u->v路径上的点，所有连向子节点的边染成col2；
2.将u->v路径上的点，所有连向父节点的边染成col1；
3.将LCA(u,v)连向父节点的边染成col2。
那么本题的操作实际有四种：链修改、链查询、修改一条链上所有连向子节点的边、换根+子树修改。
除了链修改指向子节点的边，其它都是树剖模板（换根见BZOJ3083）。
因为是改所有指向子节点的边，所以也可以树剖维护。用to_son[x]表示x指向儿子的轻边的颜色，用另一棵线段树维护（注意只是轻边，重边要单独在第一棵树上改）。
除此之外，在第一棵线段树上维护每个点x到fa[x]的边的颜色。
这样查询时，对于重链可以直接在第一棵线段树上查；对于轻边（top[x]->fa[top[x]]）的颜色，需要区分是第一棵树上top[x]的值还是第二棵树上fa[top[x]]的值。修改时再带一个时间优先级即可。
要修改的链是一样的，且to_son[x]只会单点查（切换重链时）（也是单点修改），所以只要一棵线段树同时维护两种标记就行了。
复杂度\(O(m\log^2n)\)。
另外单点查完全可以用非递归。
边界（dfn+/-1）问题要注意。（会不会还有锅啊。。）

//358ms	20428KB
#include 
#include 
#include 
#define fir first
#define sec second
#define mp std::make_pair
#define pr std::pair//time val
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
typedef long long LL;
const int N=1e5+5;

int n,Enum,H[N],nxt[N<<1],to[N<<1],fa[N],dep[N],sz[N],son[N],top[N],dfn[N],Index,ref[N],out[N];
char IN[MAXIN],*SS=IN,*TT=IN;
struct Segment_Tree
{
	#define ls rt<<1
	#define rs rt<<1|1
	#define lson l,m,ls
	#define rson m+1,r,rs
	#define S N<<2
	int cnt[S][3],sz[S];
	pr tag1[S],tag2[S];
	#undef S

	#define Update(rt) cnt[rt][0]=cnt[ls][0]+cnt[rs][0], cnt[rt][1]=cnt[ls][1]+cnt[rs][1], cnt[rt][2]=cnt[ls][2]+cnt[rs][2]
	#define Cov1(rt,v) cnt[rt][0]=0, cnt[rt][1]=0, cnt[rt][2]=0, cnt[rt][v.sec]=sz[rt], tag1[rt]=v
	#define Cov2(rt,v) tag2[rt]=v
	inline void PushDown(int rt)
	{
		int l=ls,r=rs;
		if(tag1[rt].fir) Cov1(l,tag1[rt]), Cov1(r,tag1[rt]), tag1[rt].fir=0;
		if(tag2[rt].fir) Cov2(l,tag2[rt]), Cov2(r,tag2[rt]), tag2[rt].fir=0;
	}
	void Build(int l,int r,int rt)
	{
		cnt[rt][0]=sz[rt]=r-l+1;
		if(l!=r)
		{
			int m=l+r>>1;
			Build(lson), Build(rson);
		}
	}
	void ModifyI(int l,int r,int rt,int L,int R,pr v)//为了常数 粘了仨Modify→_→
	{
		if(L<=l && r<=R) {Cov1(rt,v); return;}
		PushDown(rt);
		int m=l+r>>1;
		if(L<=m) ModifyI(lson,L,R,v);
		if(m>1;
		p<=m ? Modify1(lson,p,v) : Modify1(rson,p,v);
		Update(rt);
	}
	void Modify2(int l,int r,int rt,int L,int R,pr v1,pr v2)
	{
		if(L<=l && r<=R) {Cov1(rt,v1), Cov2(rt,v2); return;}
		PushDown(rt);
		int m=l+r>>1;
		if(L<=m) Modify2(lson,L,R,v1,v2);
		if(m>1, p<=m?(r=m,rt=ls):(l=m+1,rt=rs);
		}
		return id==1?tag1[rt]:tag2[rt];
	}
	int QueryI(int l,int r,int rt,int L,int R,int c)
	{
		if(L<=l && r<=R) return cnt[rt][c];
		PushDown(rt);
		int m=l+r>>1;
		if(L<=m)
			if(mmx) mx=sz[v], son[x]=v;
		}
}
void DFS2(int x,int tp)
{
	top[x]=tp, dfn[x]=++Index, ref[Index]=x;
	if(son[x])
	{
		DFS2(son[x],tp);
		for(int i=H[x],v; i; i=nxt[i])
			if((v=to[i])!=fa[x]&&v!=son[x]) DFS2(v,v);
	}
	out[x]=Index;
}
int Query(int u,int v,int c)
{
	int ans=0,tp;
	while(top[u]!=top[v])
	{
		if(dep[top[u]]t2.fir?(t1.sec==c):(t2.sec==c);
		u=fa[tp];
	}
	if(dep[u]

#include 
#include 
#include 
#include 
#define mp std::make_pair
#define pr std::pair
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define mod 998244353
#define Mod(x) x>=mod&&(x-=mod)
typedef long long LL;
const int N=1e6+5;

int n,m,outd[N],ind[N],pw[N];
char IN[MAXIN],*SS=IN,*TT=IN;
struct Graph
{
	int Enum,H[N],nxt[N],to[N],len[N];
	void AE(int u,int v,int w)
	{
		to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;
	}
}G,R;
struct Node
{
	int id;
	pr x;
	inline bool operator <(const Node &a)const
	{
		return x<=a.x;
	}
}A[N];

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
void Toposort()
{
	static int q[N],f[N],lev[N],lev2[N],pre[N],sum[N],dgr[N];
	static bool inq[N],vis[N];

	int h=0,t=0;
	memcpy(dgr,outd,sizeof dgr);
	for(int i=1; i<=n; ++i) if(!dgr[i]) q[++t]=i;
	while(hlev[x])
					lev[v]=lev[x], pre[v]=G.len[i];//, sum[v]=sum[x]*29%mod+pre[v], Mod(sum[v]);
				else if(lev[v]==lev[x]&&pre[v]>G.len[i])
					pre[v]=G.len[i];//, sum[v]=sum[x]*29%mod+pre[v], Mod(sum[v]);
//				printf("v:%d lev[v]=%d pre[v]=%d pw[%d]=%d\n",v,lev[v],pre[v],f[v],pw[f[v]]);
			}
			if(!--dgr[v]) q[++t]=v;
		}
	}
//	puts("");
//	for(int i=1; i<=n; ++i) printf("%d:lev:%d lev2:%d pre:%d\n",i,lev[i],lev2[i],pre[i]); puts("");

	memcpy(dgr,outd,sizeof dgr);
	h=0,t=0;
	for(int i=1; i<=n; ++i) if(!dgr[i]) q[++t]=i;
	while(h