T4 [USACO23JAN] Tractor Paths P
唯二的两道蓝题之一,但难度至少紫黑之间。思路是这篇题解的。
首先一个贪心:跳到与当前区间相连的最靠右的区间肯定是最优的,由此倍增易得第一问。重点在于第二问的求解,我们发现这个东西很麻烦,这时候就需要一些寄巧了。具体来说,前人之述备矣。
坑点:DFS 序必须用 vector 存图,因为链式前向星存图是倒着存的,而这题我们需要用 DFS 序找所有的儿子,所以必须用 vector。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
#define lowbit(x) (x&-x)
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
string reads(){
string s=" ";
char ch=getchar();
while(!isalnum(ch))ch=getchar();
while(isalnum(ch))s+=ch,ch=getchar();
return s;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('\n'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
putchar(sf);
}
constexpr int MAXN=2e5+5;
int n,q,totl,totr,F;
string s;
struct{int l,r;}a[MAXN];
int st[MAXN];
void add(int x,int k){
while(x<=n)st[x]+=k,x+=lowbit(x);
}
int sum(int x){
int res=0;
while(x)res+=st[x],x-=lowbit(x);
return res;
}
int fa[MAXN][31],dfn[MAXN],dfncnt;
vector<int>g[MAXN];
void dfs(int u){
dfn[u]=++dfncnt;
for(int i=1;i<=F;++i)fa[u][i]=fa[fa[u][i-1]][i-1];
for(auto v:g[u])dfs(v);
}
int dis[MAXN],ans[MAXN];
struct fk{
int x,w,id;
fk(int x,int w,int id):x(x),w(w),id(id){}
};
vector<fk>qr[MAXN];
void ad(int l,int r,int L,int R,int id){
qr[r].emplace_back(R,1,id);
qr[r].emplace_back(L-1,-1,id);
qr[l-1].emplace_back(R,-1,id);
qr[l-1].emplace_back(L-1,1,id);
}
int main(){
n=read(),q=read(),s=reads();
F=log2(n);
for(int i=1;i<=n<<1;++i)
if(s[i]=='L')a[++totl].l=i;
else a[++totr].r=i;
for(int i=2,pos=1;i<=n;++i)
while(pos<i&&(i==n||a[i+1].l>a[pos].r)){
fa[pos][0]=i;
g[i].emplace_back(pos++);
}
dfs(n);
s=reads();
for(int i=1,x,y,tmp;i<=q;++i){
x=read(),y=read();
dis[i]=1;
tmp=x;
for(int j=F;~j;--j){
if(!fa[x][j]||fa[x][j]>=y)continue;
dis[i]+=1ll<<j,x=fa[x][j];
}
if(dfn[tmp]<dfn[y])ad(tmp,y,1,dfn[tmp],i),ad(tmp,y,dfn[y],n,i);
else ad(tmp,y,dfn[y],dfn[tmp],i);
}
for(int i=1;i<=n;++i){
if(s[i]=='1')add(dfn[i],1);
for(auto x:qr[i])ans[x.id]+=sum(x.x)*x.w;
}
for(int i=1;i<=q;++i)write(dis[i],' '),write(ans[i]);
return fw,0;
}
标签:Paths,qr,emplace,int,题解,back,USACO23JAN,id
From: https://www.cnblogs.com/laoshan-plus/p/18440843