A
\(n\times m\) 的网格图，初始一个数 \(o=0\)。
-
\(o=0\) 时只能上下走，\(o=1\) 时只能左右走，走一步代价为 \(1\)。
-
给出 \(k\) 个点，在这些点可以令 \(o\leftarrow o\oplus 1\)，代价为 \(1\)。
问 \((1,1)\) 到 \((n,m)\) 的最小代价。
\(n\le m\le 10^5\)，\(1\le k\le 2\times 10^5\)。
拆点建图跑最短路即可。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define N 200010
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,m,x[N],y[N],_k,k;
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
vector<pii>gx[N],gy[N];
vector<pii>e[N<<1];//goud -> 0 golr -> 1
void add(int u,int v,int w){
e[u].push_back(mp(v,w));
}
ll dist[N<<1];bool vis[N<<1];
#define pli pair<ll,int>
priority_queue<pii>q;
void dijkstra(int S){
memset(dist,0x3f,sizeof(dist));
dist[S]=0,q.push(mp(0,S));
while(!q.empty()){
int u=q.top().se;q.pop();
if(vis[u])continue;
vis[u]=true;
for(pii E:e[u]){
if(dist[E.fi]>dist[u]+E.se){
dist[E.fi]=dist[u]+E.se;
q.push(mp(-dist[E.fi],E.fi));
}
}
}
}
int main(){
n=read(),m=read(),_k=read();
x[1]=1,y[1]=1,k=1;
for(int i=1,_x,_y;i<=_k;i++){
_x=read(),_y=read();
if(_x==1&&_y==1)add(1,2,1);
else if(_x!=n||_y!=m)x[++k]=_x,y[k]=_y;
}
x[++k]=n,y[k]=m;
for(int i=1;i<=k;i++){
gx[x[i]].push_back(mp(y[i],i));
gy[y[i]].push_back(mp(x[i],i));
}
for(int i=1,len;i<=n;i++){
sort(gx[i].begin(),gx[i].end());
len=gx[i].size();
for(int j=0,u,v,up,vp;j<len-1;j++){
u=gx[i][j].se,v=gx[i][j+1].se;
up=gx[i][j].fi,vp=gx[i][j+1].fi;
add(u*2-1,v*2-1,vp-up),add(v*2-1,u*2-1,vp-up);
add(u*2-1,v*2,vp-up+1),add(v*2-1,u*2,vp-up+1);
}
}
for(int i=1,len;i<=m;i++){
sort(gy[i].begin(),gy[i].end());
len=gy[i].size();
for(int j=0,u,v,up,vp;j<len-1;j++){
u=gy[i][j].se,v=gy[i][j+1].se;
up=gy[i][j].fi,vp=gy[i][j+1].fi;
add(u*2,v*2,vp-up),add(v*2,u*2,vp-up);
add(u*2,v*2-1,vp-up+1),add(v*2,u*2-1,vp-up+1);
}
}
dijkstra(1);
ll ans=min(dist[k*2-1],dist[k*2]);
if(ans==dist[0])puts("-1");
else printf("%lld\n",ans);
return 0;
}
B
Korney Korneevich and XOR (hard version)
*2400。
问 \(\{a_n\}\) 的所有递增子序列的异或和，输出这些值。
\(1\le n\le 10^6\)，\(0\le a_i\le 5000\)。
注意到异或和在 \([0,2^{13})\) 之间，记 \(V=2^{13}-1\)。
记 \(f_i\) 为当前以 \(a\) 结尾的子序列的异或值集合，其中 \(a<i\)。
对于每个 \(a\)，对 \(b\in f_a,j\in[a+1,V]\)，将 \(a\oplus b\) 加入 \(f_j\)。
每次即值域后缀集合加点，对于异或值 \(p\) 记录 \(mx_p\) 表示未添加 \(p\) 的最大集合编号。
时间复杂度 \(O(n+V^2)\)。
点击查看代码
#include<bits/stdc++.h>
#define V 8192
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,mx[V],ans=1;
vector<int>d[V];bool vis[V];
int main(){
n=read(),vis[0]=true;
for(int i=1;i<V;i++)d[i].push_back(0),mx[i]=V-1;
for(int i=1,x;i<=n;i++){
x=read();
for(int v:d[x]){
int p=v^x;ans+=!vis[p],vis[p]=true;
while(mx[p]>x)d[mx[p]--].push_back(p);
}
d[x].clear();
}
printf("%d\n",ans);
for(int i=0;i<V;i++)
if(vis[i])printf("%d ",i);
printf("\n");
return 0;
}
C
P8313 [COCI2021-2022#4] Izbori
问 \(\{a_n\}\) 有多少区间存在绝对众数。
\(1\le n\le 2\times 10^5\)，\(1\le a_i\le 10^9\)。
典，但是没放根号做法。
-
\(O(n\sqrt{n})\) Sol
根号分治。
先离散化。对于出现次数 \(\ge\sqrt{n}\) 的数 \(x\)，将 \(x\) 赋权 \(1\)，否则为 \(-1\)，作前缀和后数对 \([l,r]\) 合法即 \(S_r>S_{l-1}\)，\(O(n\sqrt{n}+n\log n)\) 数点即可。
对于出现次数 \(<\sqrt{n}\) 的，注意到 \(\sum cnt(x)^2\sim O(n\sqrt{n})\)，考虑 \(O(1)\) 计算一段整块和两边散块的答案，维护直线交点即可。
总时间复杂度 \(O(n\sqrt{n})\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define N 200010
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,dlt,maxn,a[N],b[N],len;
int cnt[N];
vector<int>s[N];
#define lb(x) x&-x
struct Fenwick{
int c[N<<1];
void add(int x,int k){
for(;x<=n+dlt;x+=lb(x))c[x]+=k;
}
int qry(int x){
int ret=0;
for(;x;x-=lb(x))ret+=c[x];
return ret;
}
}B;
ll ans;
ll calc(int p,int q,int t){
if(t<0)return 0;
p=min(p,t),q=min(q,t);
int pos=min(t-q,p);
ll ret=1ll*q*(pos+1);
if(p>pos)ret+=1ll*t*(p-pos)-1ll*p*(p+1)/2+1ll*pos*(pos+1)/2;
return ret+p+1;
}
int main(){
n=read(),maxn=sqrt(n),dlt=n+1;
for(int i=1;i<=n;i++)
a[i]=b[i]=read();
sort(b+1,b+1+n),len=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+1+len,a[i])-b;
cnt[a[i]]++,s[a[i]].push_back(i);
}
for(int i=1;i<=len;i++){
if(cnt[i]<=maxn){
int ln=s[i].size(),l,r,L,R;
for(int j=0;j<ln;j++)
for(int k=j;k<ln;k++){
l=s[i][j],r=s[i][k];
L=j?s[i][j-1]+1:1,R=(k<ln-1)?s[i][k+1]-1:n;
ans+=calc(l-L,R-r,2*(k-j+1)-(r-l+1)-1);
}
}
else{
int sum=0;
B.add(dlt,1);
for(int j=1;j<=n;j++){
sum+=(a[j]==i)?1:-1;
ans+=B.qry(sum+dlt-1),B.add(sum+dlt,1);
}
B.add(dlt,-1),sum=0;
for(int j=1;j<=n;j++)
sum+=(a[j]==i)?1:-1,B.add(sum+dlt,-1);
}
}
printf("%lld\n",ans);
return 0;
}
-
\(O(n\log n)\) Sol
考虑对每个 \(w\) 单独求解。对 \(w\) 赋权 \(1\)，否则为 \(0\)，那么 \([l+1,r]\) 合法即 \(2(S_r-S_l)>r-l\Rightarrow 2S_r-r>2S_l-l\).
方便地，记 \(P_i=2S_i-i\).
发现相邻的 \(P_i\) 一定相差 \(1\) 或 \(-1\)。维护这些 \(P_i\) 形成的若干递减的等差数列，能够发现所有 \(w\) 的总段数是 \(O(n)\) 的。
发现即支持区间加求二阶前缀和。