100+100+20+17，T3 按理说应该想到考虑两部分分别的贡献的，明明这个套路很常见。
5k：就喜欢这种数据结构专场，多来点。
A.origen
先前缀和，以下 \(p_i\) 表示前缀异或和。
考虑将一个数 \(k\) 二进制差分，假设拆成 \(2^a+2^b+2^c\)，则 \(k^2=(2^a+2^b+2^c)\times(2^a+2^b+2^c)\)，也就是指数两两结合。
所以一个数的平方就相当于 \(k^2=\sum\limits_{i=0}^{\lfloor\log_2{k^2}\rfloor} 2^i\times \sum\limits_{j=0}^{i} [k\operatorname{bitand} 2^j][k\operatorname{bitand} 2^{i-j}]\)。所以我们考虑统计所有原序列子区间异或和的第 \(x\) 位与第 \(y\) 位。
设 \(f_{i,x,y,0/1,0/1}\) 为在 \(1\sim i\) 当中，\(a_i\) 的第 \(x,y\) 二进制位为 \(0/1,0/1\) 的个数，\(ans_i\) 为所有 \(k^2\) 中 \(2^i\) 的个数。
设 \(w1=[p_i\operatorname{bitand} 2^x],w2=[p_i\operatorname{bitand} 2^y]\)。
有转移 \(ans_{x+y}=ans_{x+y}+f_{i-1,x,y,w1\oplus 1,w2\oplus 1},f_{i,x,y,w1,w2}=f_{i-1,x,y,w1,w2}+1\)。
最后统计答案即可，第一维可滚掉，时间复杂度 \(O(n\log^2 n)\)。
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2e5+10,MOD=998244353;
int n,a[MAXN];long long ans[50],f[20][20][2][2];
int main()
{
freopen("origen.in","r",stdin);
freopen("origen.out","w",stdout);
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
cin>>n;for(int i=1;i<=n;++i) cin>>a[i],a[i]^=a[i-1];
for(int x=0;x<18;++x)
for(int y=0;y<18;++y)
f[x][y][0][0]=1;
for(int i=1;i<=n;++i)
{
for(int x=0;x<18;++x)
for(int y=0;y<18;++y)
{
ans[x+y]+=f[x][y][(a[i]>>x)&1^1][(a[i]>>y)&1^1];
f[x][y][(a[i]>>x)&1][(a[i]>>y)&1]++;
ans[x+y]%=MOD;
}
}
long long ANS=0,P=1;
for(int i=0;i<36;++i)
{
ANS+=P*ans[i]%MOD;
P=P*2%MOD;
}
cout<<ANS%MOD<<'\n';return 0;
}
B.competition
考虑统计所有组“每组中不能做出来的题数之和”\(sum\)，记总组数 \(N=\dfrac{n(n+1)}{2}\)，最终答案为 \(\dfrac{Nm-sum}{N}\)。
如果你从 \(1\to n\) 扫描，维护出来每道题最后能做出来的时间 \(t_i\)，那么你选择的以 \(i\) 结尾的区间的不能做出来的题数之和就等于 \(im-\sum\limits_{j=1}^{m} t_j\)，（\(im\) 因为有 \(i\) 个区间）。
要维护全局和，区间赋值，线段树即可，动态开点被卡空间，离散化即可。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int MAXN=1e6+10,MOD=1e9+7;
int n,cnt=1,tot,p;ll m,l[MAXN],r[MAXN],ans;
ll a[MAXN<<1],b[MAXN<<2],len[MAXN<<2];
struct tree{int num,add,len;}t[MAXN<<4];
void build(ll l,ll r,int p)
{
if(l==r){t[p].len=len[l];return ;}
ll mid=(l+r)>>1;
build(l,mid,p<<1),build(mid+1,r,p<<1|1);
t[p].len=(t[p<<1].len+t[p<<1|1].len)%MOD;return ;
}
inline void change(ll l,ll r,int p,ll x,ll y,ll z)
{
if(x<=l&&y>=r)
{
t[p].num=1ll*t[p].len*z%MOD;
t[p].add=z;return ;
}
ll mid=(l+r)>>1;
if(t[p].add)
{
t[p<<1].num=1ll*t[p<<1].len*t[p].add%MOD;
t[p<<1|1].num=1ll*t[p<<1|1].len*t[p].add%MOD;
t[p<<1].add=t[p].add,t[p<<1|1].add=t[p].add;
t[p].add=0;
}
if(x<=mid) change(l,mid,p<<1,x,y,z);
if(y>mid) change(mid+1,r,p<<1|1,x,y,z);
t[p].num=(t[p<<1].num+t[p<<1|1].num)%MOD;return ;
}
inline long long ksm(long long a,int b)
{
long long ans=1;
while(b)
{
if(b&1) ans=ans*a%MOD;
a=a*a%MOD,b>>=1;
}
return ans;
}
int main()
{
freopen("competition.in","r",stdin);
freopen("competition.out","w",stdout);
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>l[i]>>r[i],a[++tot]=l[i],a[++tot]=r[i];
a[++tot]=0,a[++tot]=m;sort(a+1,a+1+tot);
for(int i=1;i<=tot;++i)
{
if(i!=1&&a[i]==a[i-1]) continue;
if(i!=1&&a[i]!=a[i-1]+1)
b[++p]=a[i-1]+1,len[p]=(a[i]-a[i-1]-1)%MOD;
b[++p]=a[i],len[p]=1;
}
for(int i=1;i<=n;++i)
l[i]=lower_bound(b+1,b+1+p,l[i])-b,
r[i]=lower_bound(b+1,b+1+p,r[i])-b;
build(1,p,1);
for(int i=1;i<=n;++i)
{
change(1,p,1,l[i],r[i],i);
ans+=(m%MOD*i%MOD-t[1].num+MOD)%MOD;
}
ll N=1ll*n*(n+1)/2%MOD;
cout<<(m%MOD*N%MOD-ans%MOD+MOD)%MOD*ksm(N,MOD-2)%MOD<<'\n';
return 0;
}
C.tour
发现最多连成一棵树，每次就是在森林中选取两个树合并。
拆路径，记 \(L=lca(x,y)\)，\(x\to y\) 拆成 \(x\to L,L\to y\)。
记 \(dis_i\) 为 \(i\) 到根路径上的权值和。
第一段 \(i\in x\to L\) 满足条件，等价于 \(dis_x-dis_i\geq a_i\)。
第二段 \(i\in L\to y\) 满足条件，等价于 \((dis_x-dis_L+a_L)+(dis_i-dis_L-a_i)\geq a_i\)。
移项，主席树维护点到根信息，转换成树链上小于等于某个数个数。合并启发式合并暴力重构，感觉平凡，但我赛时没想到。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int MAXN=1e5+10,INF=500010000;
int testmode,lastans,n,q,a[MAXN],dis[MAXN];
int dep[MAXN],f[MAXN][20],fa[MAXN],siz[MAXN];
vector <int> v[MAXN];
struct segment_tree
{
int root[MAXN],cnt;
struct tree{int num,ls,rs;}t[MAXN<<8];
inline void change(int l,int r,int p,int q,int x)
{
t[q].ls=t[p].ls,t[q].rs=t[p].rs;
if(l==r){t[q].num=t[p].num+1;return ;}
int mid=(l+r)>>1;
if(x<=mid) change(l,mid,t[p].ls,t[q].ls=++cnt,x);
else change(mid+1,r,t[p].rs,t[q].rs=++cnt,x);
t[q].num=t[t[q].ls].num+t[t[q].rs].num;return ;
}
inline int query(int l,int r,int p,int q,int x,int y)
{
if(x<=l&&y>=r) return t[q].num-t[p].num;
int mid=(l+r)>>1,ans=0;
if(x<=mid) ans+=query(l,mid,t[p].ls,t[q].ls,x,y);
if(y>mid) ans+=query(mid+1,r,t[p].rs,t[q].rs,x,y);
return ans;
}
}X,Y;
inline void work(int i,int fa)
{
X.change(-INF,INF,X.root[fa],X.root[i]=++X.cnt,a[i]+dis[i]);
Y.change(-INF,INF,Y.root[fa],Y.root[i]=++Y.cnt,2*a[i]-dis[i]);
return ;
}
inline int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) x=f[x][__lg(dep[x]-dep[y])];
if(x==y) return x;
for(register int i=__lg(dep[x]);i>=0;--i)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
void dfs(int x,int fa=0)
{
for(int i=0;i<=__lg(dep[x]);++i) f[x][i]=0;
dep[x]=dep[fa]+1,dis[x]=dis[fa]+a[x];
f[x][0]=fa,work(x,fa);
for(int i=1;i<=__lg(dep[x]);++i)
f[x][i]=f[f[x][i-1]][i-1];
for(int y:v[x]) if(y!=fa) dfs(y,x);
return ;
}
inline int find(int x){return (x==fa[x])?x:fa[x]=find(fa[x]);}
int main()
{
freopen("tour.in","r",stdin);
freopen("tour.out","w",stdout);
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
cin>>testmode>>n>>q;
for(int i=1;i<=n;++i)
cin>>a[i],dep[i]=1,dis[i]=a[i],work(i,0),fa[i]=i,siz[i]=1;
while(q--)
{
int opt,x,y;cin>>opt>>x>>y;
if(testmode) x^=lastans,y^=lastans;
if(opt==0)
{
v[x].push_back(y),v[y].push_back(x);
int fax=find(x),fay=find(y);
if(siz[fax]<siz[fay]) swap(x,y),swap(fax,fay);
siz[fax]+=siz[fay],fa[fay]=fax,dfs(y,x);
}
else
{
int L=lca(x,y),ans=0;
ans+=X.query(-INF,INF,X.root[f[L][0]],X.root[x],-INF,dis[x]);
ans+=Y.query(-INF,INF,Y.root[L],Y.root[y],-INF,dis[x]+a[L]-2*dis[L]);
cout<<(lastans=ans)<<'\n';
}
}
return 0;
}
D.abstract
好像有意思，先咕。
标签：13,return,NOIP,int,26,MAXN,ans,include,dis From： https://www.cnblogs.com/int-R/p/NOIP-A-26.html