C++14(g++5.4) 解法, 执行用时: 668ms, 内存消耗: 59588K, 提交时间: 2019-03-25 22:39:20
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
// #include<unordered_map>
using namespace std;
int bin[40],lg[1<<21];
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,int>
#define PB push_back
#define vc vector
inline void chmax(int &x,const int y) {x=x>y?x:y;}
inline void chmin(int &x,const int y) {x=x<y?x:y;}
const int MAX_N=1e5+10;
struct BIT
{
int bit[MAX_N];BIT(){memset(bit,0,sizeof bit);}
// void add(int x,int c) {bit[x]+=c;}
// int sum(int x) {int ans=0;while(x>=1) ans+=bit[x],x--;return ans;}
int lowbit(int x) {return x&-x;}
void add(int x,int c) {while(0<x and x<MAX_N) bit[x]+=c,x+=lowbit(x);}
int sum(int x) {int ans=0;while(x>=1) ans+=bit[x],x-=lowbit(x);return ans;}
}bit;
struct LCT
{
struct Nod{int son[2],fa,col,siz;bool tg;}p[MAX_N];
LCT(){memset(p,0,sizeof p);for(int i=1;i<MAX_N;i++) p[i].siz=1;}
#define lc p[x].son[0]
#define rc p[x].son[1]
void pushup(int x) {p[x].siz=1+p[lc].siz+p[rc].siz;}
void pushdown(int x) {if(p[x].tg) p[x].tg=0,p[lc].col=p[rc].col=p[x].col,p[lc].tg=p[rc].tg=1;}
#define son(x) (p[p[x].fa].son[1]==x)
bool isrt(int x) {return p[p[x].fa].son[son(x)]!=x;}
void rotate(int x)
{
int f=p[x].fa,ff=p[f].fa;if(!isrt(f)) p[ff].son[son(f)]=x;
int w=son(x),ts=p[x].son[w^1];p[x].son[w^1]=f;p[f].son[w]=ts;
p[x].fa=ff;p[f].fa=x;if(ts) p[ts].fa=f;pushup(f);pushup(x);
}
int tmp[MAX_N];
void splay(int x)
{
int tot=0,t=x;while(!isrt(t)) tmp[++tot]=t,t=p[t].fa;
pushdown(t);for(int i=tot;i>=1;i--) pushdown(tmp[i]);
for(int fa=p[x].fa;!isrt(x);rotate(x),fa=p[x].fa)
if(!isrt(fa)) son(x)^son(fa)?rotate(x):rotate(fa);
}
void access(int x,int col)
{
int lst=0,tmp=x;
while(x>0)
{
splay(x);
bit.add(p[x].col,-p[lc].siz-1);
p[x].son[1]=lst;if(lst) p[lst].fa=x;pushup(x);
lst=x;x=p[x].fa;
}
splay(tmp);p[tmp].tg=1;p[tmp].col=col;
bit.add(col,p[tmp].siz);
}
}lct;
vector<int> son[MAX_N];
int dep[MAX_N],mm[MAX_N*2][21],dfn[MAX_N],id=0;
void dfs(int x,int fa)
{
dep[x]=dep[fa]+1;lct.p[x].fa=fa;dfn[x]=++id;mm[id][0]=x;
for(int t=0;t<(int)son[x].size();t++)
{
int y=son[x][t];if(y==fa) continue;
dfs(y,x);mm[++id][0]=x;
}
}
int gmin(int x,int y) {return dep[x]<dep[y]?x:y;}
int getlca(int x,int y)
{
x=dfn[x],y=dfn[y];if(x>y) swap(x,y);
int t=lg[y-x+1];return gmin(mm[x][t],mm[y-bin[t]+1][t]);
}
int gg[MAX_N][21];
int gettop(int l,int r)
{
int t=lg[r-l+1];return getlca(gg[l][t],gg[r-bin[t]+1][t]);
}
int tmp[MAX_N],a[MAX_N],rk[MAX_N];//映射
bool cmp(int x,int y) {return a[x]<a[y];}
vector<pr> qes[MAX_N];int ans[MAX_N*5];
void main()
{
int n=qread(),q=qread();
for(int i=1;i<=n;i++) a[tmp[i]=i]=qread();
sort(tmp+1,tmp+n+1,cmp);sort(a+1,a+n+1);
for(int i=1;i<=n;i++) rk[tmp[i]]=i;
for(int i=2;i<=n;i++) {int x=rk[qread()],y=rk[qread()];son[x].PB(y),son[y].PB(x);/*printf("%d %d\n",x,y);*/}
dfs(1,0);
for(int i=1;i<=20;i++) for(int j=1;j<=id-bin[i]+1;j++) mm[j][i]=gmin(mm[j][i-1],mm[j+bin[i-1]][i-1]);
for(int i=1;i<=n;i++) gg[i][0]=i;
for(int i=1;i<=20;i++) for(int j=1;j<=n-bin[i]+1;j++) gg[j][i]=getlca(gg[j][i-1],gg[j+bin[i-1]][i-1]);
for(int i=1;i<=q;i++)
{
int l=lower_bound(a+1,a+n+1,qread())-a;
int r=upper_bound(a+1,a+n+1,qread())-a-1;
qes[r].PB(MP(l,i));
}
for(int r=1;r<=n;r++)
{
lct.access(r,r);
for(int t=0;t<(int)qes[r].size();t++)
{
int l=qes[r][t].FR,id=qes[r][t].SE;
// if(l<=r) printf("l=%d r=%d lca=%d\n",l,r,dep[gettop(l,r)]);
if(l<=r) ans[id]=bit.sum(r)-bit.sum(l-1)-(dep[gettop(l,r)]-1);
}
}
for(int i=1;i<=q;i++) writeln(ans[i]);
}
};
int main()
{
srand(time(0));
bin[0]=1;for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
lg[1]=0;for(int i=2;i<(1<<21);i++) lg[i]=lg[i>>1]+1;
mine::main();
}
C++11(clang++ 3.9) 解法, 执行用时: 573ms, 内存消耗: 52840K, 提交时间: 2019-03-16 15:29:00
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')w=0,ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
#define pi pair<int,int>
#define mk make_pair
const int N=5e5+5;
int n,q,a[N],p[N],rk[N],ans[N];vector<pi>Q[N];
namespace bit{
int c[N];
void modify(int x,int v){
while(x<=n)c[x]+=v,x+=x&-x;
}
int query(int x){
int res=0;
while(x)res+=c[x],x^=x&-x;
return res;
}
}
namespace lct{
int fa[N],ch[2][N],sz[N],col[N],tag[N];
bool son(int x){return x==ch[1][fa[x]];}
bool isrt(int x){return x!=ch[0][fa[x]]&&x!=ch[1][fa[x]];}
void up(int x){sz[x]=sz[ch[0][x]]+1+sz[ch[1][x]];}
void rot(int x){
int y=fa[x],z=fa[y],c=son(x);
ch[c][y]=ch[c^1][x];if(ch[c][y])fa[ch[c][y]]=y;
fa[x]=z;if(!isrt(y))ch[son(y)][z]=x;
ch[c^1][x]=y;fa[y]=x;up(y);
}
void cover(int x,int v){col[x]=tag[x]=v;}
void down(int x){
if(tag[x])cover(ch[0][x],tag[x]),cover(ch[1][x],tag[x]),tag[x]=0;
}
void alldown(int x){if(!isrt(x))alldown(fa[x]);down(x);}
void splay(int x){
alldown(x);
for(int y=fa[x];!isrt(x);rot(x),y=fa[x])
if(!isrt(y))son(x)^son(y)?rot(x):rot(y);
up(x);
}
void access(int x,int v){
int y=0;
while(x){
splay(x);ch[1][x]=0;up(x);
if(col[x])bit::modify(col[x],-sz[x]);
ch[1][x]=y,up(x);
y=x;x=fa[x];
}
cover(y,v);bit::modify(col[y],sz[y]);
}
}
namespace tree{
int fa[N],dep[N],sz[N],top[N],lg[N],gg[18][N];
vector<int>E[N];
void link(int x,int y){E[x].push_back(y);E[y].push_back(x);}
void dfs1(int u,int f){
fa[u]=lct::fa[u]=f;dep[u]=dep[f]+1;sz[u]=1;
for(int v:E[u])if(v!=f)dfs1(v,u),sz[u]+=sz[v];
}
void dfs2(int u,int f){
top[u]=f;gg[0][u]=u;int son=0;
for(int v:E[u])if(v!=fa[u])son=sz[v]>sz[son]?v:son;
if(son)dfs2(son,f);
for(int v:E[u])if(v!=fa[u]&&v!=son)dfs2(v,v);
}
int lca(int u,int v){
while(top[u]!=top[v])
if(dep[top[u]]>dep[top[v]])u=fa[top[u]];
else v=fa[top[v]];
return dep[u]<dep[v]?u:v;
}
void init(){
dfs1(1,0);dfs2(1,1);
for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;
for(int j=1;j<=lg[n];++j)
for(int i=1;i+(1<<j)-1<=n;++i)
gg[j][i]=lca(gg[j-1][i],gg[j-1][i+(1<<j-1)]);
}
int get(int l,int r){
int k=lg[r-l+1];
return dep[lca(gg[k][l],gg[k][r-(1<<k)+1])];
}
}
bool cmp(int i,int j){return a[i]<a[j];}
int main(){
n=gi();q=gi();
for(int i=1;i<=n;++i)a[p[i]=i]=gi();
sort(p+1,p+n+1,cmp);sort(a+1,a+n+1);
for(int i=1;i<=n;++i)rk[p[i]]=i;
for(int i=1;i<n;++i)tree::link(rk[gi()],rk[gi()]);
tree::init();
for(int i=1;i<=q;++i){
int l=lower_bound(a+1,a+n+1,gi())-a;
int r=upper_bound(a+1,a+n+1,gi())-a-1;
Q[r].push_back(mk(i,l));
}
for(int i=1;i<=n;++i){
lct::access(i,i);
for(pi x:Q[i]){
int id=x.first,l=x.second;
if(l>i)ans[id]=0;
else ans[id]=bit::query(i)-bit::query(l-1)-tree::get(l,i)+1;
}
}
for(int i=1;i<=q;++i)printf("%d\n",ans[i]);return 0;
}
的点 i 为关键点