BZOJ-1146: [CTSC2008]网络管理Network
2018-10-16 本文已影响0人
AmadeusChan
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1146
极端恶心的一道模版题。
解法一：
这道题很容易就可以联想到主席树，但是主席树维护的是序列，那么就直接做成DFS序列，每个点拆成一个进点(in[v])和出点(out[v]),然后对于每个进点+w[i],每个出点-w[i],又要支持修改，那么就树状数组套主席树，然后直接在主席树上二分，时空复杂度均为O(n log^2 n)，然后我就很兴奋地敲了200+代码，结果一交上去果断MLE，然后才发现自己写的主席树占用空间都差不多500M了，果断放弃。（ORZ此法过的大神）
解法二：
树链剖分+树状数组（线段树）+平衡树+二分查找，复杂度：O(q log^4 n)，相当高的复杂度。
解法三：
树链剖分+树状数组（线段树）+主席树，复杂度O(q log^3 n),还算好写，不过我死活空间省不到161M。
解法四：
DFS序+树状数组+平衡树+二分查找，在解法一的基础上把主席树改成BST，然后二分答案，复杂度O(n log^2 n + q log^3 n),个人觉得相当好写。
代码（dfs序+BIT套SBT+二分查找，苦逼的300+行，还慢得要死）：
fcfaaf51f3deb48f59752fd3f21f3a292df5789b.jpg.png
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
#define MAXN 80010
#define MAXV 4000010
#define inf 0x7fffffff
#define lowbit(x)((-x)&x)
#define L(t) Node[t].left
#define R(t) Node[t].right
#define K(t) Node[t].key
#define S(t) Node[t].size
#define update(t) S(t)=S(L(t))+S(R(t))+1
int w[MAXN],n,m,Query[MAXN][3];
//---------------------------------Size_Balanced_Tree_Start------------------------
struct node {
int left,right,key,size;
node () {
left=right=key=size=0;
}
} Node[MAXV];
queue<int>Q;
int V=0;
void init_sbt() {
L(0)=R(0)=S(0)=0;
while (!Q.empty()) Q.pop();
}
int New() {
if (!Q.empty()) {
int v=Q.front();
Q.pop();
L(v)=R(v)=0;
return v;
}
return ++V;
}
void Recycle(int t) {
Q.push(t);
}
void left_ratote(int &t) {
int k=R(t);
R(t)=L(k); update(t);
L(k)=t; update(k);
t=k;
}
void right_ratote(int &t) {
int k=L(t);
L(t)=R(k); update(t);
R(k)=t; update(k);
t=k;
}
void maintain(int &t) {
if (S(L(L(t)))>S(R(t))) {
right_ratote(t);
maintain(R(t));
maintain(t);
return ;
}
if (S(R(L(t)))>S(R(t))) {
left_ratote(L(t));
right_ratote(t);
maintain(L(t)),maintain(R(t));
maintain(t);
return ;
}
if (S(R(R(t)))>S(L(t))) {
left_ratote(t);
maintain(L(t));
maintain(t);
return ;
}
if (S(L(R(t)))>S(L(t))) {
right_ratote(R(t));
left_ratote(t);
maintain(L(t)),maintain(R(t));
maintain(t);
return ;
}
}
void Insert(int k,int &t) {
if (!t) {
t=New();
S(t)=1,K(t)=k;
return ;
}
S(t)++;
if (k<K(t)) Insert(k,L(t)); else Insert(k,R(t));
maintain(t);
}
void Delete(int k,int &t) {
if (K(t)==k) {
if (!L(t)) {
int v=t;
t=R(t),Recycle(v);
return ;
} else {
if (!R(t)) {
int v=t;
t=L(t),Recycle(v);
return ;
} else {
right_ratote(t);
Delete(k,R(t));
}
}
} else if (k<K(t)) Delete(k,L(t)); else Delete(k,R(t));
update(t);
maintain(t);
}
int Rank(int k,int t) {
if (!t) return 0;
if (k<K(t)) return S(R(t))+1+Rank(k,L(t)); else return Rank(k,R(t));
}
//---------------------------------Size_Balanced_Tree_End--------------------------
//-------------------------------Tree_Start----------------------------------------
struct edge {
int t;
edge *next;
edge () {
next=NULL;
}
} *head[MAXN];
void Tree_init() {
memset(head,0,sizeof(head));
}
void Add(int s,int t) {
edge *p=new(edge);
p->t=t,p->next=head[s];
head[s]=p;
}
void AddEdge(int s,int t) {
Add(s,t),Add(t,s);
}
int In[MAXN],Out[MAXN],Index=0;
bool f[MAXN];
void dfs(int v) {
In[v]=++Index,f[v]=false;
for (edge *p=head[v];p;p=p->next) if (f[p->t]) dfs(p->t);
Out[v]=++Index;
}
//-------------------------------Tree_End------------------------------------------
//-------------------------Binary_Index_Tree_Start---------------------------------
int bit[MAXN*2][2];
void bit_insert(int x,int y,int t) {
for (;x<=2*n;x+=lowbit(x)) Insert(y,bit[x][t]);
}
void bit_delete(int x,int y,int t) {
for (;x<=2*n;x+=lowbit(x)) Delete(y,bit[x][t]);
}
void bit_init() {
memset(bit,0,sizeof(bit));
for (int i=0;i++<n;) bit_insert(In[i],w[i],0),bit_insert(Out[i],w[i],1);
}
int rank_bit(int k,int x) {
int rec=0;
for (int i=x;i;i-=lowbit(i)) rec+=Rank(k,bit[i][0]),rec-=Rank(k,bit[i][1]);
return rec;
}
void Change(int v,int k) {
bit_delete(In[v],w[v],0),bit_delete(Out[v],w[v],1);
bit_insert(In[v],k,0),bit_insert(Out[v],k,1);
w[v]=k;
}
//-------------------------Binary_Index_Tree_End-----------------------------------
//--------------------------Sort_Start---------------------------------------------
int b[MAXN*2],c[MAXN*2],N=0,Nn=0;
bool cmp(int x,int y) {
return x>y;
}
void Sort() {
sort(c+1,c+Nn+1,cmp);
for (int i=0;i++<Nn;) if (i==1||c[i]!=c[i-1]) b[++N]=c[i];
}
//--------------------------Sort_End-----------------------------------------------
//-------------------------------LCA_Start(Tarjan)---------------------------------
struct saver {
saver *next;
int t,r;
saver () {
next=NULL;
}
} *fro[MAXN];
void lca_insert(int s,int t,int r) {
saver *p=new(saver);
p->next=fro[s],p->t=t,p->r=r;
fro[s]=p;
}
int father[MAXN],lca[MAXN];
int Find(int x) {
int i=x,j=x;
for (;father[i];i=father[i]) ;
while (father[j]) {
int k=father[j];
father[j]=i;
j=k;
}
return i;
}
void Tarjan(int v) {
f[v]=false;
for (saver *p=fro[v];p;p=p->next) if (!f[p->t]) lca[p->r]=Find(p->t);
for (edge *p=head[v];p;p=p->next) if (f[p->t]) {
Tarjan(p->t);
father[Find(p->t)]=v;
}
}
void Tarjan_lca() {
memset(fro,0,sizeof(fro));
memset(father,0,sizeof(father));
memset(f,true,sizeof(f));
for (int i=0;i++<m;) if (Query[i][0]) lca_insert(Query[i][1],Query[i][2],i),lca_insert(Query[i][2],Query[i][1],i);
Tarjan(1);
}
//-------------------------------LCA_End-------------------------------------------
//------------------------------Main_Function--------------------------------------
int rank_path(int v,int u,int LCA,int k) {
int rec=rank_bit(k,In[v])+rank_bit(k,In[u])-2*rank_bit(k,In[LCA]);
return rec+(w[LCA]>k?1:0);
}
int main() {
scanf("%d%d",&n,&m);
c[++Nn]=-inf,c[++Nn]=inf;
for (int i=0;i++<n;) scanf("%d",&w[i]),c[++Nn]=w[i];
Tree_init();
for (int i=0;i++<n-1;) {
int s,t;
scanf("%d%d",&s,&t);
AddEdge(s,t);
}
memset(f,true,sizeof(f));
dfs(1);
for (int i=0;i++<m;) {
scanf("%d%d%d",&Query[i][0],&Query[i][1],&Query[i][2]);
if (!Query[i][0]) c[++Nn]=Query[i][2];
}
bit_init(),Sort(),Tarjan_lca();
for (int i=0;i++<m;) {
if (!Query[i][0]) Change(Query[i][1],Query[i][2])
; else {
if (rank_path(Query[i][1],Query[i][2],lca[i],-inf)<Query[i][0]) printf("invalid request!\n")
; else {
int l=1,r=N;
while (r-l>1) {
int mid=(l+r)>>1;
int sum=rank_path(Query[i][1],Query[i][2],lca[i],b[mid]);
if (sum>=Query[i][0]) r=mid; else l=mid;
}
printf("%d\n",b[l]);
}
}
}
return 0;
}
