1001 循环位移
双哈希
1002 星星
简单 \(dp\) ，使用 \(dp[i][j]\) 表示前 \(i\) 轮获取 \(j\) 颗星星的最小贡献。时间复杂度 \(O(\sum n\times k)\) 。
1003 树
树上启发式合并，当时只知道原理，没写过题目，不应该按照自己理解瞎写的，应该先简单学一下……
考虑将一个节点 \(j\) 添加进一堆已有的点中，贡献变化。
对于所有小于该点点权的贡献和 \(\sum_{w_{p}< w_{j}}w_{j}\times(w_{j}-w_{p})=k\times w_{j}^{2}-w_{j}\times\sum_{w_{p}< w_{j}}w_{p}\) ；
对于所有大于该点点权的贡献和 $\sum_{w_{p}> w_{j}}w_{p}\times(w_{p}-w_{j})=\sum_{w_{p}> w_{j}}w_{p}^{2}-w_{j}\times\sum_{w_{p}> w_{j}}w_{p} $ 。
小于该数个数、前缀和、后缀和、后缀平方和的修改与查询都可以通过维护树状数组实现，总时间复杂度 \(O(nlog^{2}n)\) 。剩余部分就是简单的树上启发式合并的思路。
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define endl '\n'
const int N=5e5+5;
const int M=1e6;
struct BIT
{
int t[M+6];
int lowbit(int x) { return x&(-x); }
//单点修改
void update(int pos,int k) {
for(int i=pos;i<=M;i+=lowbit(i)) t[i]+=k;
}
//区间查询
int ask(int pos) {
int ans=0;
for(int i=pos;i;i-=lowbit(i)) ans+=t[i];
return ans;
}
}B[3];
vector<int>g[N];
//子树大小与重儿子编号
int siz[N],son[N];
//dfs序
int l[N],r[N],id[N],y[N],tot;
void dfs1(int u,int f)
{
l[u]=id[u]=++tot;
y[tot]=u;
siz[u]=1;
for(auto v:g[u])
{
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(!son[u]||siz[v]>siz[son[u]]) son[u]=v;
}
r[u]=tot;
}
int w[N],ans,res[N];
void col(int u,int op)
{
int num=B[0].ask(w[u]),sum=B[1].ask(w[u]);
ans+=op*(w[u]*w[u]*num-w[u]*sum)*2;
int bsum=B[1].ask(M)-B[1].ask(w[u]),bpf=B[2].ask(M)-B[2].ask(w[u]);
ans+=op*(bpf-bsum*w[u])*2;
B[0].update(w[u],op*1);
B[1].update(w[u],op*w[u]);
B[2].update(w[u],op*w[u]*w[u]);
}
void add(int u) { col(u,1); }
void del(int u) { col(u,-1); }
void dfs2(int u,int f,int keep)
{
for(auto v:g[u])
{
if(v==f||v==son[u]) continue;
dfs2(v,u,0); //先计算轻儿子的答案
}
if(son[u]) dfs2(son[u],u,1); //重儿子贡献保留
for(auto v:g[u])
{
if(v==f||v==son[u]) continue;
for(int i=l[v];i<=r[v];i++) {
add(y[i]); //添加轻的贡献儿子
}
}
add(u);
res[u]=ans;
if(keep==0) {
for(int i=l[u];i<=r[u];i++) {
del(y[i]);
}
}
}
void solve()
{
int n;cin>>n;
for(int i=1;i<n;i++)
{
int u,v;cin>>u>>v;
g[u].push_back(v),g[v].push_back(u);
}
for(int i=1;i<=n;i++) cin>>w[i];
int ret=0;
dfs1(1,0);
dfs2(1,0,0);
for(int i=1;i<=n;i++) ret^=res[i];
cout<<ret<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T=1;//cin>>T;
while(T--) solve();
return 0;
}
1004 传送
线段树分治+可撤销并查集+lazytag。
首先对于一个“xxx在xxx时间点出现在xxx时间点消失，问若干个时间点的状态”这类问题，其实已经摆明使用线段树分治解决。
首先简单介绍线段树分治。
线段树分治是对时间线开一棵线段树，将所有操作离线之后把它们拍到这棵线段树上，之后从上往下对这棵线段树进行 \(dfs\) ，每遇到一个区间就将其中的所有操作信息贡献到答案中，等到递归到 \(l==r\) 时即可得到一个时间点的信息。一个区间结束之后再将它的贡献消除以防止对后面区间的影响即可。所以一般需要保证维护信息的数据结构是可撤销的。
不过一般线段树分治都是处理该时间点的所有信息，此题要求每个点在与1联通的时刻和的异或和。因此需要使用 \(lazytag\) 。
首先对于一个时间点，我们想要给所有与1联通的点都加上这个时间点的值，但是有肯定不能遍历，所以选择只给这个集合的根节点加上这个时间点的值，也就是 \(lazytag\) 。那这个集合里其他的点呢？因为线段树分治是有回滚的，在整个 \(dfs\) 结束后所有的操作都会被回滚掉，所以在回滚的过程中将所有的点都加上其根节点的 \(lazytag\) 。还有一个问题就是在按秩合并的时候，需要将 \(size\) 更小的一方的 \(lazytag\) 减去大的集合的 \(lazytag\) ，因为这里面已有的贡献不属于小的集合。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define endl '\n'
#define ls k<<1
#define rs k<<1|1
const int N=6e5+5;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
int n,lz[N];
struct BCJ
{
int n,fa[N],siz[N];
void init(int x)
{
n=x;
for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
}
int find(int x)
{
// 不能使用路径压缩
return x==fa[x]?x:find(fa[x]);
}
void merge(int x,int y,stack<pii>&sta)
{
x=find(x),y=find(y);
if(x==y) return;
if(siz[x]<siz[y]) swap(x,y);
lz[y]-=lz[x];
fa[y]=x;
siz[x]+=siz[y];
sta.push({x,y});
}
void roll_back(stack<pii>&sta)
{
while(!sta.empty())
{
auto [x,y]=sta.top();
sta.pop();
lz[y]+=lz[x];
siz[x]=siz[y];
fa[y]=y;
}
}
}b;
vector<pii>t[N<<2];
void update(int k,int l,int r,int p,int q,int u,int v)
{
if(p<=l&&r<=q)
{
t[k].push_back({u,v});
return;
}
int mid=(l+r)>>1;
if(p<=mid) update(ls,l,mid,p,q,u,v);
if(q>mid) update(rs,mid+1,r,p,q,u,v);
}
void dfs(int k,int l,int r)
{
stack<pii>s;
for(auto [u,v]:t[k]) b.merge(u,v,s);
if(l!=r)
{
int mid=(l+r)>>1;
dfs(ls,l,mid);
dfs(rs,mid+1,r);
}
else lz[b.find(1)]+=l;
b.roll_back(s);
}
signed main()
{
int m;
n=read(),m=read();
b.init(n);
for(int i=1;i<=m;i++)
{
int x,y,l,r;
x=read(),y=read(),l=read(),r=read();
update(1,1,n,l,r,x,y);
}
dfs(1,1,n);
int res=0;
for(int i=1;i<=n;i++) res^=lz[i];
write(res);
return 0;
}
1006 立方序列
一个子序列出现次数的立方等价于选三个序列他们恰好相同的方案数。
前缀和优化dp（待补）
1007 三元环
cdq分治，竞赛图（任意两点之间存在一条有向边）
考虑3个点的有向图，要么成环，要么有一个点入度为2（如果可以注意到这个性质，公式就非常好出），假设第i个点的入度为 \(d_{i}\) ，答案为 \(C_{n}^{3}-\sum _{i=1}^{n} C_{d_{i}}^{2}\) ， \(d_{i}\) 用cdq分治求得。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define endl '\n'
const int N=2e5+5;
const int mod=998244353;
struct node
{
int x,y,z,ans,w;
}a[N];
int n;
il int cmpx(node a,node b)
{
if(a.x==b.x)
{
if(a.y==b.y) return a.z<b.z;
return a.y<b.y;
}
return a.x<b.x;
}
il int cmpy(node a,node b)
{
if(a.y==b.y) return a.z<b.z;
return a.y<b.y;
}
struct BIT
{
int n,t[N];
il int lowbit(int x) { return x&(-x); }
il void update(int pos,int k) { for(int i=pos;i<=n;i+=lowbit(i)) t[i]+=k; }
il int ask(int pos)
{
int ans=0;
for(int i=pos;i;i-=lowbit(i)) ans+=t[i];
return ans;
}
}t;
il void cdq(int l,int r)
{
if(l==r) return;
int mid=(l+r)>>1;
cdq(l,mid);cdq(mid+1,r);
sort(a+l,a+mid+1,cmpy);
sort(a+mid+1,a+r+1,cmpy);
int j=l;
for(int i=mid+1;i<=r;i++)
{
while(a[j].y<a[i].y && j<=mid)
t.update(a[j].z,a[j].w),j++;
a[i].ans+=t.ask(a[i].z-1);
}
for(int i=l;i<j;i++)
t.update(a[i].z,-a[i].w);
j=r;
for(int i=mid;i>=l;i--)
{
while(a[j].y>a[i].y && j>mid)
t.update(a[j].z,a[j].w),j--;
a[i].ans-=t.ask(n)-t.ask(a[i].z);
}
for(int i=r;i>j;i--)
t.update(a[i].z,-a[i].w);
}
int f[N],g[N];
void solve()
{
cin>>n;
t.n=n;
for(int i=1;i<=n;i++) cin>>f[i];
for(int i=1;i<=n;i++)
{
cin>>g[i];
a[i]={i,f[i],g[i],0,1};
a[i].ans+=(n-a[i].x);
}
sort(a+1,a+n+1,cmpx); cdq(1,n);
ll ans=1ll*n*(n-1)*(n-2)/6;
for(int i=1;i<=n;i++)
{
int d=a[i].ans;
ans-=1ll*(d-1)*d>>1;
}
cout<<ans<<'\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T=1;//cin>>T;
while(T--) solve();
return 0;
}
1008 位运算
对每个位考虑为 \(0/1\) 的所有方案数，然后直接相乘。
1012 并
队友单刷（tql）。
标签：钉耙,int,siz,void,编程,mid,2024,sum,define From： https://www.cnblogs.com/mhw-mathcode/p/18334462