【SP10628 COT - Count on a tree】题解

· · 题解

Description

静态区间第 k 小，肯定是主席树，但是我不会，所以我就用树上莫队 + 值域分块 A 了这道题。

不的不说，还真有点卡常，喜提最劣解。

温馨提示 ： 这个题好像不能用 C ++ 11，14，17 来交，我交了后一直 waiting，建议用 C ++。

Solution

首先这个题目的数据范围也没说，我为了保险，还是写了个离散化，后来在原站上的知是在 int 范围内。

我用的是值域分块和树上莫队，查询区间第 k 小，

树上莫队不会的请去 SP10707 学一下。

讲一下值域分块，我们分块的时候借用莫队的分块即可，树上莫队的区间长度是 2n，肯定能够盛下离散化后的值域。

所以只需要值域分块即可。

之后用两个数组 cnt[i] 和 tmp[i]，cnt 数组来存每个数字出现多少次，tmp 数组来存每个块中有多少个数字。

查询的时候，枚举每个块，之后查询即可。

int Work(int k)
{
  int Sum = 0;//统计前面的数的个数
  for(int i = 1;i <= T;i ++) {
    if(Sum + tmp[i] < k) {Sum += tmp[i];continue;}
    //如果这个块中的数字全部加起来都没有 k 大，就肯定不在这个块里面
    else {
      for(int j = L[i];j <= R[i];j ++) {
        Sum += cnt[j];
        //不断加上数值，直到达到目标。
        if(Sum >= k) return j;
      }
    }
  }
}

那么这是我们离散化后的数值，我们是要求原数值，我搞了个 map 来存，从 \color{red}{TLE \ \ on \ \ 4} 改到了 \color{red}{TLE \ \ on \ \ 11}，连平板电视都用上了，实在改不动了，才想到用数组，/ch。

我建立了四个数组，a,b,c,d，a 数组离散化，b 数组帮助离散化，c 数组是原来的 a 数组的复制版，d 数组用来建立离散化后的值和原数的对应关系。

就这么卡过了。

献上我巨长的代码。(逃

Code

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
const int Maxk = 1e6 + 10;
int n,size,cnt1,m,Q,cnts,cntq,T;
int st[Maxk],ed[Maxk],sum[Maxk];
int tot[Maxk],dfn[Maxk << 1],top[Maxk];
int deep[Maxk],fa[Maxk],used[Maxk],cnt[Maxk];
int a[Maxk],son[Maxk],tmp[Maxk],b[Maxk],c[Maxk],d[Maxk];
int head[Maxk],L[Maxk],R[Maxk],block[Maxk];
int ans[Maxk],Ans;
struct node{
  int from;
  int to;
  int next;
}e[Maxk << 1];
struct Query{
  int l;
  int r;
  int pos;
  int k_;
  int Lca_;
}s[Maxk];
struct Modify {
  int past;
  int Now;
}q[Maxk];
inline int read()
{
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) f |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48),ch = getchar();
    return f ? -x : x;
}
void add_edge(int from,int to)//连边 
{
  e[++ cnt1].to = to;
  e[cnt1].from = from;
  e[cnt1].next = head[from];
  head[from] = cnt1;
  return;
}

void BLOCK()
{
  sort(b + 1,b + n + 1);
  int tot = unique(b + 1,b + n + 1) - b - 1;
  for(int i = 1;i <= n;i ++) {
    a[i] = lower_bound(b + 1,b + tot + 1,a[i]) - b;//离散化
    d[a[i]] = c[i];//建立一个关系
  }
  int nn = n << 1;//莫队的分块和值域分块
  //这里我估计重新开一个长为 n 的块可能会更快，但我不想写了。
  int len = pow(nn,0.6666667);
  T = nn / len;
  for(int i = 1;i <= T;i ++) {
    L[i] = (i - 1) * len + 1;
    R[i] = i * len; 
  }
  if(R[T] < nn) T ++,L[T] = R[T - 1] + 1,R[T] = nn;
  for(int i = 1;i <= T;i ++) 
    for(int j = L[i];j <= R[i];j ++)
      block[j] = i;
  return; 
}

void dfs1(int now,int f)//树剖的 dfs1
{
  deep[now] = deep[f] + 1;
  fa[now] = f;
  st[now] = ++ size;
  dfn[size] = now;
  tot[now] = 1;
  for(int i = head[now];i;i = e[i].next) {
    int y = e[i].to;
    if(y == f) continue;
    dfs1(y,now);
    tot[now] += tot[y];
    if(tot[y] > tot[son[now]]) son[now] = y;
  }
  ed[now] = ++size;
  dfn[size] = now;
}

void dfs2(int now,int topfa)//树剖的 dfs2
{
  top[now] = topfa;
  if(!son[now]) return ;
  dfs2(son[now],topfa);
  for(int i = head[now];i;i = e[i].next) {
    int y = e[i].to;
    if(y == fa[now] || y == son[now]) continue;
    dfs2(y,y);
  }
}

int LCA(int x,int y)
//树上莫队判断是否需要加上 LCA
{
  while(top[x] ^ top[y]) {
    if(deep[top[x]] < deep[top[y]]) swap(x,y);
    x = fa[top[x]];
  }
  return deep[x] < deep[y] ? x : y;
}
inline bool CMP(Query a,Query b)//莫队排序
{
  return block[a.l] ^ block[b.l] ? block[a.l] < block[b.l] : a.r < b.r;
}
void Prepare()//处理询问，离线储存
{
  for(int i = 1;i <= Q;i ++) {
    int x = read(),y = read(),k = read();
    if(st[x] > st[y]) swap(x,y);
    int Lca = LCA(x,y);
    s[i].k_ = k;
    s[i].pos = i;
    if(Lca == x) {//同一个子树内不用 LCA
      s[i].l = st[x];
      s[i].r = st[y];
    }
    else {
      s[i].l = ed[x];//否则需要 LCA
      s[i].r = st[y];
      s[i].Lca_ = Lca;
    }
  }
  return;
}

void add(int x)
{
  cnt[x] ++;//这个值的个数 ++ 
  tmp[block[x]] ++;//
}
void del(int x)
{
  cnt[x] --;
  tmp[block[x]] --; 
}

void calc(int x)
{
  used[x] ? del(a[x]) : add(a[x]);
  used[x] ^= 1;
}

int Work(int k)//值域分块的查询第 k 小
{
  int Sum = 0;
  for(int i = 1;i <= T;i ++) {
    if(Sum + tmp[i] < k) {Sum += tmp[i];continue;}
    else {
      for(int j = L[i];j <= R[i];j ++) {
        Sum += cnt[j];
        if(Sum >= k) return j;
      }
    }
  }
}

void Solve()//莫队
{
  sort(s + 1,s + Q + 1,CMP);
  int l = 1,r = 0;
  for(int i = 1;i <= Q;i ++) {
    int ql = s[i].l;
    int qr = s[i].r;
    while(l < ql) calc(dfn[l ++]);
    while(l > ql) calc(dfn[-- l]);
    while(r > qr) calc(dfn[r --]);
    while(r < qr) calc(dfn[++ r]);
    if(s[i].Lca_) calc(s[i].Lca_);
    ans[s[i].pos] = d[Work(s[i].k_)];
    if(s[i].Lca_) calc(s[i].Lca_);
  }
  for(int i = 1;i <= Q;i ++) printf("%d\n",ans[i]);
  return;
}

signed main()
{
  n = read(),Q = read();
  for(int i = 1;i <= n;i ++) a[i] = b[i] = c[i] = read();//读入
  for(int i = 1;i <= n - 1;i ++) {//连边
    int x = read(),y = read();
    add_edge(x,y);
    add_edge(y,x);
  }
  BLOCK();//分块 + 离散化
  dfs1(1,0);//树剖
  dfs2(1,1);
  Prepare();//读入询问
  Solve();//莫队解决
  return 0;
}