Ynoi 2016これは私自身が発明したものです
2830 ワード
Description
link
ルート変更と指定された2つのポイントをサポートし、サブツリーで重み値が同じスキーマ数を満たす
Solution
遠い国(+)簡単な質問
(上の2つともタイトル名です)
推奨カード定数テクニック:無駄な質問をすべて削除する(つまり、(l_1、l_2)と(1)または(0)比の関係の場合)
他にもstlや関数を使わず、手書きなどは使いにくい(コンニャクの個人的な経験)
Code
link
ルート変更と指定された2つのポイントをサポートし、サブツリーで重み値が同じスキーマ数を満たす
Solution
遠い国(+)簡単な質問
(上の2つともタイトル名です)
推奨カード定数テクニック:無駄な質問をすべて削除する(つまり、(l_1、l_2)と(1)または(0)比の関係の場合)
他にもstlや関数を使わず、手書きなどは使いにくい(コンニャクの個人的な経験)
Code
#include
using namespace std;
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
const int N=5e5+10;
int a[N],b[N],m,n,T,bl[N],fa[N][25],dep[N],st[N],ed[N],head[N],cnt,tot,dfn,block,ans[N*5],p[N];
struct node{
int nxt,to;
}e[N<<1];
inline void add(int u,int v)
{
e[++cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt;
return ;
}
inline void dfs(int x,int fat)
{
dep[x]=dep[fat]+1; st[x]=++dfn; fa[x][0]=fat; p[dfn]=x;
for(int i=1;(1<x.r;
}
}q[N*16];
int res,l=0,r=0,s1[N],s2[N],opt,rt=1,num;
inline void add1(int x)
{
s1[x]++; res+=s2[x];
return ;
}
inline void del1(int x)
{
s1[x]--; res-=s2[x];
return ;
}
inline void del2(int x)
{
s2[x]--; res-=s1[x];
return ;
}
inline void add2(int x)
{
s2[x]++; res+=s1[x];
return ;
}
int t1[10],t2[10],now,sz,x,y;
inline void calc(int x)
{
if(x==rt)
{
t1[++now]=1,t2[now]=n;
}
else if(!(st[x]<=st[rt]&&ed[rt]<=ed[x]))
{
t1[++now]=st[x]; t2[now]=ed[x];
}
else
{
int p=dep[rt]-dep[x]-1,y=rt;
for(int i=0;i<18;++i)
{
if(p&(1<r1||l2>r2||l1<1||l2<1||r2>n||l2>n) continue;
if(l1>1&&l2>1) q[++tot].fl=1,q[tot].id=num,q[tot].l=l1-1,q[tot].r=l2-1;
q[++tot].fl=1; q[tot].id=num; q[tot].l=r1; q[tot].r=r2;
if(l1>1) q[++tot].fl=-1,q[tot].id=num,q[tot].r=r2,q[tot].l=l1-1;
if(l2>1) q[++tot].fl=-1,q[tot].id=num,q[tot].r=r1,q[tot].l=l2-1;
}
}
}
}
for(int i=1;i<=tot;++i) if(q[i].l>q[i].r) swap(q[i].l,q[i].r);
sort(q+1,q+tot+1);
for(int i=1;i<=tot;++i)
{
while(lq[i].l) del1(a[p[l]]),--l;
while(rq[i].r) del2(a[p[r]]),--r;
ans[q[i].id]+=q[i].fl*res;
}
for(int i=1;i<=num;++i) printf("%d
",ans[i]);
return 0;
}
}
signed main(){return yspm::main();}