上午学考的时候口胡了前三题，然而 T4 看不懂样例。
树上的数
思博题。dfs 即可。容易发现每个被删掉的节点只会扫一遍。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct node{
int v,next;
}edge[5000010];
int n,m,ans,last,t,head[5000010];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
bool v[5000010];
void dfs(int x){
if(v[x])return;
v[x]=true;ans--;
for(int i=head[x];i;i=edge[i].next)dfs(edge[i].v);
}
int main(){
scanf("%d%d",&n,&m);ans=n;
int a,b,f=1;scanf("%d%d",&a,&b);
for(int i=2;i<=n;i++){
add(f,i);
f=((1ll*f*a+b)^19760817)%i+1;
}
int q,x,y;scanf("%d%d%d",&q,&x,&y);
for(int i=1;i<=m;i++){
dfs(q);last^=ans;
q=(((1ll*q*x+y)^19760817)^(i+1<<1))%(n-1)+2;
}
printf("%d\n",last);
return 0;
}
时代的眼泪
一眼换根。然后考虑怎么换。
首先每个节点的贡献就是子树内比它小的节点个数。根节点的答案容易得到，考虑换根时候的变化。原来的根少了一棵子树，新的根变成了全部的部分。那么每个节点记录子树内比自己小的和比父亲小的节点个数算就行了。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int read(){
int x=0;char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=10*x+ch-48,ch=getchar();
return x;
}
int n,q,w[1000010],lsh[1000010],c[1000010];
struct node{
int v,next;
}edge[2000010];
int t,head[2000010];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
#define lowbit(x) (x&-x)
void update(int x,int val){
while(x<=n)c[x]+=val,x+=lowbit(x);
}
int query(int x){
int sum=0;while(x)sum+=c[x],x-=lowbit(x);return sum;
}
int val[1000010],fa[1000010];
long long dp[1000010];
void dfs1(int x,int f){
val[x]-=query(w[x]-1);
if(f)fa[x]-=query(w[f]-1);
update(w[x],1);
for(int i=head[x];i;i=edge[i].next)if(edge[i].v!=f)dfs1(edge[i].v,x);
val[x]+=query(w[x]-1);
if(f)fa[x]+=query(w[f]-1);
dp[1]+=val[x];
}
void dfs2(int x,int f){
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
dp[edge[i].v]=dp[x]+query(w[edge[i].v]-1)-val[edge[i].v]-fa[edge[i].v];
dfs2(edge[i].v,x);
}
}
}
int main(){
n=read();q=read();
for(int i=1;i<=n;i++)w[i]=read(),lsh[i]=w[i];
sort(lsh+1,lsh+n+1);
int cnt=unique(lsh+1,lsh+n+1)-lsh-1;
for(int i=1;i<=n;i++)w[i]=lower_bound(lsh+1,lsh+cnt+1,w[i])-lsh;
for(int i=1;i<n;i++){
int u=read(),v=read();add(u,v);add(v,u);
}
dfs1(1,0);dfs2(1,0);
while(q--){
int x=read();printf("%lld\n",dp[x]);
}
return 0;
}
传统艺能
首先不同子序列的一个 dp 是设 \(dp_{i,j}\) 为到 \(i\) 以 \(j\) 字符结尾的方案数。转移显然：
- \(s_i=j\)：\(dp_{i,j}=1+\sum_kdp_{i-1,k}\)。
- \(s_i\neq j\)：\(dp_{i,j}=dp_{i-1,j}\)。
放到区间上还带修，考虑矩阵。发现这个东西容易写成矩阵维护，那线段树写就行了。轻微卡常。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
const int mod=998244353;
int n,m;
char s[100010];
struct node{
int a[5][5];
node(){memset(a,0,sizeof(a));}
node operator*(const node &s)const{
node ret;
for(int i=1;i<=4;i++)for(int j=1;j<=4;j++)for(int k=1;k<=4;k++)ret.a[i][j]=(ret.a[i][j]+1ll*a[i][k]*s.a[k][j])%mod;
return ret;
}
}tmp[3],tree[400010];
void pushup(int rt){
tree[rt]=tree[lson]*tree[rson];
}
void build(int rt,int l,int r){
if(l==r){
tree[rt]=tmp[s[l]-'A'];return;
}
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
pushup(rt);
}
void update(int rt,int L,int R,int pos,int val){
if(L==R){
tree[rt]=tmp[val];return;
}
int mid=(L+R)>>1;
if(pos<=mid)update(lson,L,mid,pos,val);
else update(rson,mid+1,R,pos,val);
pushup(rt);
}
node query(int rt,int L,int R,int l,int r){
if(l<=L&&R<=r)return tree[rt];
int mid=(L+R)>>1;
node val;val.a[1][1]=val.a[2][2]=val.a[3][3]=val.a[4][4]=1;
if(l<=mid)val=val*query(lson,L,mid,l,r);
if(mid<r)val=val*query(rson,mid+1,R,l,r);
return val;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m>>s+1;
for(int i=1;i<=4;i++)tmp[0].a[i][i]=tmp[1].a[i][i]=tmp[2].a[i][i]=1;
for(int i=1;i<=4;i++)tmp[0].a[1][i]=tmp[1].a[2][i]=tmp[2].a[3][i]=1;
build(1,1,n);
while(m--){
int od;cin>>od;
if(od==1){
int pos;char od[5];cin>>pos>>od;
update(1,1,n,pos,od[0]-'A');
}
else{
int l,r;cin>>l>>r;
node ret=query(1,1,n,l,r);
int ans=(1ll*ret.a[1][4]+ret.a[2][4]+ret.a[3][4])%mod;
printf("%d\n",ans);
}
}
return 0;
}
铺设道路
完全看不懂样例。
首先最少轮数就是差分数组所有正值的和。这是普及-。然后考虑怎么构造方案。
发现每次操作就相当于把差分数组 \(b\) 的 \(b_l,b_r\) 变为 \(b_l+1,b_r-1\)，代价 \((r-l)^2\)。那么每次一定要 \(b_l<0,b_r>0\) 才能使得次数最少。
那么我们有一个贪心：如果值最大的话，就让 \(r\) 和最右边的 \(l\) 匹配。反之和最左边的 \(l\) 匹配。据说是对的，证明邻项交换。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#define int long long
using namespace std;
const int mod=1000000007;
int n,ans,b[300010],d[300010],tmp[300010];
int l,r,q[300010];
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld",&d[i]),b[i]=d[i]-d[i-1],ans+=max(b[i],0ll),tmp[i]=b[i];
n++;b[n]=tmp[n]=-d[n-1];
printf("%lld\n",ans);ans=0;
l=1,r=0;
for(int i=1;i<=n;i++){
if(b[i]>0)q[++r]=i;
else{
int x=-b[i];
while(x){
if(b[q[r]]<=x)ans+=(i-q[r])*(i-q[r])%mod*b[q[r]]%mod,x-=b[q[r]],r--;
else ans+=(i-q[r])*(i-q[r])%mod*x%mod,b[q[r]]-=x,x=0;
ans%=mod;
}
}
}
printf("%lld\n",ans);ans=0;
for(int i=1;i<=n;i++)b[i]=tmp[i];
l=1,r=0;
for(int i=1;i<=n;i++){
if(b[i]>0)q[++r]=i;
else{
int x=-b[i];
while(x){
if(b[q[l]]<=x)ans+=(i-q[l])*(i-q[l])%mod*b[q[l]]%mod,x-=b[q[l]],l++;
else ans+=(i-q[l])*(i-q[l])%mod*x%mod,b[q[l]]-=x,x=0;
ans%=mod;
}
}
}
printf("%lld\n",ans);
return 0;
}