前言
从这一次到 71 都是多校联考了，尽管考的不咋样。。
T1 数据恢复
解题思路
这个题真的是。。
先声明一个点，对于优先队列以及 set 都是在某个元素插入的时候进行比较，但是在之后如果修改比较条件的话也不会改变它的位置。。（好像只有我不知道）
对于上述情况我们可以用 set 删掉再加入一遍，或者建立一个合并后的假点。。
对于这个题而言对于一个点如果它的依赖已经可行直接计入贡献，否则就把它所在联通快和它父亲的联通快相连新的 \(a,b\) 值就是两个的和，同时还要多出来一个 \(a_x\times b_{fa_x}\) 的贡献。
直接并查集维护。。
code
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=5e6+10;
int n,ans,cnt,sum,fa[N],fat[N],a[N],b[N];
bool vis[N],jud[N];
struct Node
{
int id;
inline bool friend operator < (Node x,Node y)
{
return b[x.id]*a[y.id]<b[y.id]*a[x.id];
}
};
priority_queue<Node> q;
int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
signed main()
{
freopen("data.in","r",stdin); freopen("data.out","w",stdout);
n=read(); vis[0]=true; cnt=n;
for(int i=2;i<=n;i++) fat[i]=read();
for(int i=1;i<=4*n;i++) fa[i]=i;
for(int i=1;i<=n;i++) a[i]=read(),b[i]=read(),sum+=a[i];
for(int i=1;i<=n;i++) q.push((Node){i});
while(!q.empty())
{
int x=q.top().id; q.pop();
if(jud[x]) continue;
if(!vis[find(fat[x])])
{
ans+=a[x]*b[find(fat[x])]; cnt++;
a[cnt]=a[x]+a[find(fat[x])];
b[cnt]=b[x]+b[find(fat[x])];
jud[find(fat[x])]=true;
fat[cnt]=fat[find(fat[x])];
fa[find(fat[x])]=fa[x]=cnt;
q.push((Node){cnt});
continue;
}
sum-=a[x];
ans+=sum*b[x];
vis[x]=true;
}
printf("%lld",ans);
return 0;
}
T2 下落的小球
解题思路
听 fengwu 说好像和移球游戏的思路有一点像...
对于一颗子树而言它的球一定不会掉在子树外。
因此有子树根节点下来的小球的数量也是一定的，并且两者操作有先后顺序，因此就是两个多重集排列。
对于每一个不同的节点计算对于答案的贡献。
code
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e6+10,mod=1e9+7;
int n,ans=1,fa[N],siz[N],cnt[N],fac[N],ifac[N];
int tot=1,head[N],ver[N<<1],nxt[N<<1];
void add_edge(int x,int y)
{
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
int power(int x,int y,int p=mod)
{
int temp=1;
while(y)
{
if(y&1) temp=temp*x%p;
x=x*x%p; y>>=1;
}
return temp;
}
void dfs(int x)
{
int temp=0;
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i]; dfs(to);
siz[x]+=siz[to]; cnt[x]+=cnt[to];
ans=ans*ifac[siz[to]]%mod*ifac[cnt[to]-siz[to]]%mod;
}
if(head[x]) ans=ans*fac[siz[x]]%mod*fac[cnt[x]-siz[x]]%mod; siz[x]++;
}
signed main()
{
freopen("ball.in","r",stdin); freopen("ball.out","w",stdout);
n=read(); fac[0]=ifac[0]=1;
for(int i=2;i<=n;i++) fa[i]=read(),add_edge(fa[i],i);
for(int i=1;i<=n;i++) cnt[i]=read();
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
ifac[n]=power(fac[n],mod-2);
for(int i=n-1;i>=1;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
dfs(1); printf("%lld",ans);
return 0;
}
T3 消失的运算符
大坑未补
T4 古老的序列问题
解题思路
分治，对于每一个子区间计算对于每一个询问答案。
维护四颗线段树，分别给加进去的值乘上 1,min,max,min*max
先处理左区间的最大值最小值，然后对于左区间建线段树，暴扫右区间三指针分别扫出来满足最小值条件，最大值条件，同时满足的区间。
分别计算在相应问题区间贡献，同时开一个数组记录一下这个区间的贡献，解决问题区间覆盖整个子区间的答案。
code
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"
#define ls x<<1
#define rs x<<1|1
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e5+10,mod=1e9+7;
int n,m,s[N],ans[N],f[N<<2],minn[N],maxn[N];
inline void add(int &x,int val){x+=val;if(x>=mod)x-=mod;}
struct Node
{
int l,r,id;
inline bool friend operator < (Node x,Node y){return x.r<y.r;}
};
vector<Node> v[N<<2];
struct Segment_Tree
{
int num[N];
struct Node{int dat,laz,bas;}tre[N<<2];
inline void push_up(int x){tre[x].dat=(tre[ls].dat+tre[rs].dat)%mod;}
inline void push_down(int x)
{
if(!tre[x].laz) return ;
add(tre[ls].laz,tre[x].laz); add(tre[ls].dat,tre[x].laz*tre[ls].bas%mod);
add(tre[rs].laz,tre[x].laz); add(tre[rs].dat,tre[x].laz*tre[rs].bas%mod);
tre[x].laz=0;
}
inline void build(int x,int l,int r)
{
tre[x].laz=tre[x].dat=0;
if(l==r) return tre[x].bas=num[l],void();
int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r);
tre[x].bas=(tre[ls].bas+tre[rs].bas)%mod;
}
inline void insert(int x,int l,int r,int L,int R,int val)
{
if(L<=l&&r<=R) return add(tre[x].dat,tre[x].bas*val%mod),add(tre[x].laz,val),void();
int mid=(l+r)>>1; push_down(x);
if(L<=mid) insert(ls,l,mid,L,R,val);
if(R>mid) insert(rs,mid+1,r,L,R,val);
push_up(x);
}
inline int query(int x,int l,int r,int L,int R)
{
if(L<=l&&r<=R) return tre[x].dat;
int mid=(l+r)>>1,sum=0; push_down(x);
if(L<=mid) add(sum,query(ls,l,mid,L,R));
if(R>mid) add(sum,query(rs,mid+1,r,L,R));
push_up(x); return sum;
}
}T[4];
void solve(int pos,int l,int r)
{
if(l==r)
{
f[pos]=s[l]*s[l]%mod;
for(int i=0;i<v[pos].size();i++) add(ans[v[pos][i].id],f[pos]);
return ;
}
int mid=(l+r)>>1,poi=0,x=mid+1,y=mid+1,z=mid+1,mx=s[mid+1],mn=s[mid+1];
sort(v[pos].begin(),v[pos].end()); maxn[mid]=minn[mid]=s[mid];
while(poi<v[pos].size()&&v[pos][poi].r<=mid) poi++;
for(int i=mid-1;i>=l;i--) minn[i]=min(minn[i+1],s[i]),maxn[i]=max(maxn[i+1],s[i]);
fill(T[0].num+l,T[0].num+mid+1,1);
for(int i=l;i<=mid;i++) T[1].num[i]=maxn[i],T[2].num[i]=minn[i],T[3].num[i]=maxn[i]*minn[i]%mod;
for(int i=0;i<=3;i++) T[i].build(1,l,mid);
for(int i=mid+1;i<=r;i++)
{
mx=max(mx,s[i]); mn=min(mn,s[i]);
while(x>l&&minn[x-1]>=mn&&maxn[x-1]<=mx) x--;
while(y>l&&minn[y-1]>=mn) y--;
while(z>l&&maxn[z-1]<=mx) z--;
if(x<=mid) T[0].insert(1,l,mid,x,mid,mx*mn%mod);
if(y<x) T[1].insert(1,l,mid,y,x-1,mn);
if(z<x) T[2].insert(1,l,mid,z,x-1,mx);
if(y<x&&y>l) T[3].insert(1,l,mid,l,y-1,1);
if(z<x&&z>l) T[3].insert(1,l,mid,l,z-1,1);
while(poi<v[pos].size()&&v[pos][poi].r==i)
if(v[pos][poi].l>mid||(v[pos][poi].l==l&&v[pos][poi].r==r)) poi++;
else{for(int j=0;j<=3;j++) add(ans[v[pos][poi].id],T[j].query(1,l,mid,v[pos][poi].l,mid));poi++;}
}
for(int i=0;i<=3;i++) add(f[pos],T[i].query(1,l,mid,l,mid));
for(int i=0;i<v[pos].size();i++)
{
if(v[pos][i].l==l&&v[pos][i].r==r) continue;
if(v[pos][i].r<=mid) v[pos<<1].push_back(v[pos][i]);
else if(v[pos][i].l>mid) v[pos<<1|1].push_back(v[pos][i]);
else
{
v[pos<<1].push_back((Node){v[pos][i].l,mid,v[pos][i].id});
v[pos<<1|1].push_back((Node){mid+1,v[pos][i].r,v[pos][i].id});
}
}
solve(pos<<1,l,mid); solve(pos<<1|1,mid+1,r);
add(f[pos],(f[pos<<1]+f[pos<<1|1])%mod);
for(int i=0;i<v[pos].size();i++)
if(v[pos][i].l==l&&v[pos][i].r==r)
add(ans[v[pos][i].id],f[pos]);
}
signed main()
{
freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout);
n=read(); m=read(); for(int i=1;i<=n;i++) s[i]=read();
for(int i=1,l,r;i<=m;i++) l=read(),r=read(),v[1].push_back((Node){l,r,i});
solve(1,1,n); for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
return 0;
}