Super Mario
题意：n个数，m次询问，每次询问(L,R,H)，输出区间[L,R]中小于等于H的数有多少个。在求区间第k大的基础上，加上一个二分就行了。对区间[0, R-L+1]进行二分，第k大的数和H相比，寻找答案。
//还有一种较为简单的做法，将H转换为离散的数后，直接在相减后的线段树里进行区间查询即可。
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
struct num{
int val, idx, ser;
}nums[maxn];
int n, m;
struct tree{
int left, right, val;
}tree[maxn*20];
int top;
int root[maxn];
int ser[maxn];
inline int build(int l, int r){
int tmp = ++top;
if (l==r){
tree[top].val = 0;
return tmp;
}
int mid = (l+r)>>1;
tree[tmp].left = build(l, mid);
tree[tmp].right = build(mid+1, r);
tree[tmp].val = 0;
return tmp;
}
inline int add(int src, int l, int r, int target_idx){
int tmp = ++top;
if (l==r){
tree[tmp].val = tree[src].val + 1;
return tmp;
}
int mid = (l+r)>>1;
if (mid >= target_idx){
tree[tmp].left = add(tree[src].left, l, mid, target_idx);
tree[tmp].right = tree[src].right;
}else{
tree[tmp].right = add(tree[src].right, mid+1, r, target_idx);
tree[tmp].left = tree[src].left;
}
tree[tmp].val = tree[tree[tmp].left].val + tree[tree[tmp].right].val;
return tmp;
}
inline int search(int rt1, int rt2, int l, int r, int k){
if (l==r){
return l;
}
int x = tree[tree[rt2].left].val - tree[tree[rt1].left].val;
int y = tree[tree[rt2].right].val - tree[tree[rt1].right].val;
int mid = (l+r)>>1;
if (x >= k) return search(tree[rt1].left, tree[rt2].left, l, mid, k);
return search(tree[rt1].right, tree[rt2].right, mid+1, r, k-x);
}
inline int read(){
int x=0; char ch = getchar();
while (ch<'0' || ch>'9') ch = getchar();
while (ch>='0' && ch<='9'){
x = x*10 + ch-'0';
ch = getchar();
}
return x;
}
inline bool cmp1(struct num a, struct num b){
if (a.val != b.val) return a.val < b.val;
return a.idx < b.idx;
}
inline bool cmp2(struct num a, struct num b){
return a.idx < b.idx;
}
int main(){
int t, L, R, H, k;
int l, r, mid;
int cas = 0;
t = read();
while (t--){
top = 0;
n = read(), m = read();
for (int i=1; i<=n; i++){
nums[i].val = read();
nums[i].idx = i;
}
sort (nums+1, nums+n+1, cmp1);
for (int i=1; i<=n; i++){
nums[i].ser = i;
ser[i] = nums[i].val;
}
sort (nums+1, nums+n+1, cmp2);
root[0] = build(1, n);
for (int i=1; i<=n; i++)
root[i] = add(root[i-1], 1, n, nums[i].ser);
printf ("Case %d:\n", ++cas);
for (int i=1; i<=m; i++){
L = read()+1, R = read()+1, H = read();
l = 0, r = R-L+1;
while (l<r){
mid = ((l+r)>>1) + ((l+r)&1);
int tmp = ser[search(root[L-1], root[R], 1, n, mid)];
if (tmp <= H) l = mid;
else r = mid-1;
}
printf ("%d\n", l);
}
}
return 0;
}P2633 Count on a tree
主席树+LCA。对每个结点结点线段树，表示从该结点到根节点路径上所有结点的权值建立起来的线段树。
要求(u, v)路径上第k小值，只需求线段树s[u]+s[v]-s[LCA(u,v)]-s[fa[LCA(u,v)]]上的第k小值即可
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n, m;
// 树部分的变量
int val[maxn], head[maxn], lg[maxn], fa[maxn], dp[maxn][27], high[maxn];
struct edge{
int from, to, next;
}e[maxn*2];
int tot;
//离散化
struct value{
int idx, val;
}value[maxn];
// 主席树部分的变量 注意：主席树的区间是建立在离散后的权值数量上的，这和树的结点个数n相同
struct tree{
int left, right, val;
}tree[maxn*30];
int top, cnt; //top表示tree的使用情况， cnt为当前已有的线段树版本
int root[maxn];
//
int mp[maxn]; //结点i对应的主席树版本
inline int build(int l, int r){
int tmp = ++top;
if (l==r){
tree[tmp].val = 0;
return tmp;
}
int mid = (l+r)>>1;
tree[tmp].left = build(l, mid), tree[tmp].right = build(mid+1, r);
tree[tmp].val = 0;
return tmp;
}
inline int add(int src, int l, int r, int target_idx){
int tmp = ++top;
if (l==r){
tree[tmp].val = tree[src].val + 1;
return tmp;
}
int mid = (l+r)>>1;
if (mid >= target_idx){
tree[tmp].left = add(tree[src].left, l, mid, target_idx);
tree[tmp].right = tree[src].right;
}else{
tree[tmp].right = add(tree[src].right, mid+1, r, target_idx);
tree[tmp].left = tree[src].left;
}
tree[tmp].val = tree[tree[tmp].left].val + tree[tree[tmp].right].val;
return tmp;
}
inline int search(int rt1, int rt2, int rt3, int rt4, int l, int r, int k){ // u + v - LCA(u, v) - fa[LCA(u, v)]
if (l==r) return l;
int x = tree[tree[rt1].left].val + tree[tree[rt2].left].val - tree[tree[rt3].left].val - tree[tree[rt4].left].val;
int y = tree[tree[rt1].right].val + tree[tree[rt2].right].val - tree[tree[rt3].right].val - tree[tree[rt4].right].val;
int mid = (l+r)>>1;
if (x>=k) return search(tree[rt1].left, tree[rt2].left, tree[rt3].left, tree[rt4].left, l, mid, k);
else return search(tree[rt1].right, tree[rt2].right, tree[rt3].right, tree[rt4].right, mid+1, r, k-x);
}
inline int LCA(int x, int y){
if (high[y] < high[x]) swap(x, y);
while (high[y] > high[x]) y = dp[y][lg[high[y]-high[x]]-1];
if (x==y) return x;
for (int k=lg[high[x]]-1; k>=0; k--) if (dp[x][k] != dp[y][k])
x = dp[x][k], y = dp[y][k];
return dp[x][0];
}
inline void dfs(int x, int y){
fa[x] = y;
high[x] = high[y] + 1;
root[++cnt] = add(root[mp[y]], 1, n, val[x]);
mp[x] = cnt;
for (int i=head[x]; i!=-1; i=e[i].next) if (!high[e[i].to])
dfs(e[i].to, x);
return;
}
inline void Add(int from, int to){
tot++;
e[tot].from = from, e[tot].to = to, e[tot].next = head[from];
head[from] = tot;
return;
}
inline void init(){
for (int i=1; i<=n; i++) lg[i] = lg[i-1] + (1<<lg[i-1]==i);
for (int i=1; i<=n; i++) dp[i][0] = fa[i];
for (int k=1; k<=lg[n]-1; k++) for (int i=1; i<=n; i++)
dp[i][k] = dp[dp[i][k-1]][k-1];
return;
}
inline int read(){
int x = 0; char ch = getchar();
while (ch<'0' || ch>'9') ch = getchar();
while (ch>='0' && ch<='9'){
x = x*10 + ch-'0';
ch = getchar();
}
return x;
}
inline bool cmp(struct value a, struct value b){
if (a.val != b.val)
return a.val < b.val;
return a.idx < b.idx;
}
int main(){
int from, to, last = 0, u, v, k;
n = read(), m = read();
for (int i=1; i<=n; i++){
value[i].val = read();
value[i].idx = i;
}
sort (value+1, value+n+1, cmp);
for (int i=1; i<=n; i++) val[value[i].idx] = i;
top = 0;
root[0] = build(1, n);
memset (head, -1, sizeof head); tot = 0;
for (int i=1; i<n; i++){
from = read(), to = read();
Add(from, to); Add(to, from);
}
dfs(1, 0);
init();
for (int i=1; i<=m; i++){
u = read()^last, v = read(), k = read();
int tmp = LCA(u, v);
last = value[search(root[mp[u]], root[mp[v]], root[mp[tmp]], root[mp[fa[tmp]]], 1, n, k)].val;
printf ("%d\n", last);
}
return 0;
}小睿睿的兄弟
bfs序+主席树+二分
在bfs序上构建主席树，然后寻找区间使用二分。寻找kth-father使用倍增。
时间复杂度nlogn+mlog^{2}n
#include <cstdio>
#include <queue>
using namespace std;
const int maxn = 1e6+1;
struct edge{
int to, next;
}e[maxn*2];
int n, m;
int val[maxn], head[maxn], tot;
int lg[maxn], pow2[30], dp[maxn][22], depth[maxn];
int BFS[maxn], mp1[maxn];
struct tree{ //主席树数据池，left,right左右孩子，val该区间内的数值个数
int left, right, val;
}tree[maxn*25];
int root[maxn], top; //每个版本主席树在数据池中的下标 top数据池使用情况
inline int fath(int x, int k){
//k--;
while (k){
x = dp[x][lg[k]-1];
k -= pow2[lg[k]-1];
}
return x;
}
inline int src1(int l, int r, int k){
int t = fath(BFS[r], k), s = depth[BFS[r]], tmp = r;
int mid;
while (l<r){
mid = (l+r) >> 1;
if (depth[BFS[mid]] < s) l = mid+1;
else r = mid;
}
r = tmp;
while (l<r){
mid = (l+r) >> 1;
if (fath(BFS[mid], k)!=t) l = mid+1;
else r = mid;
}
return l;
}
inline int src2(int l, int r, int k){
int t = fath(BFS[l], k), s = depth[BFS[l]], tmp = l;
int mid;
while (l<r){
mid = ((l+r)>>1) + ((l+r)&1);
if (depth[BFS[mid]] > s) r = mid-1;
else l = mid;
}
l = tmp;
while (l<r){
mid = ((l+r)>>1) + ((l+r)&1);
if (fath(BFS[mid], k)!=t) r = mid-1;
else l = mid;
}
return l;
}
inline int add(int src, int l, int r, int target){
int tmp = ++top;
if (l==r){
tree[tmp].val = tree[src].val + 1;
return tmp;
}
int mid = (l+r)>>1;
if (target<=mid){
tree[tmp].left = add(tree[src].left, l, mid, target);
tree[tmp].right = tree[src].right;
}else{
tree[tmp].left = tree[src].left;
tree[tmp].right = add(tree[src].right, mid+1, r, target);
}
tree[tmp].val = tree[tree[tmp].left].val + tree[tree[tmp].right].val;
return tmp;
}
inline int search(int rt1, int rt2, int l, int r, int k){
if (k>tree[rt2].val-tree[rt1].val) return -1;
if (l==r) return l;
int x = tree[tree[rt2].left].val - tree[tree[rt1].left].val;
int y = tree[tree[rt2].right].val - tree[tree[rt1].right].val;
int mid = (l+r)>>1;
if (x>=k) return search(tree[rt1].left, tree[rt2].left, l, mid, k);
return search(tree[rt1].right, tree[rt2].right, mid+1, r, k-x);
}
inline void bfs(){
queue<int> q;
int cnt = 0, tmp;
q.push(1);
while (!q.empty()){
tmp = q.front(); q.pop();
BFS[++cnt] = tmp, mp1[tmp] = cnt;
for (int i=head[tmp]; i; i=e[i].next) if (!mp1[e[i].to])
q.push(e[i].to);
}
return;
}
inline void dfs(int u, int v){
dp[u][0] = v;
depth[u] = depth[v] + 1;
for (int i=head[u]; i; i=e[i].next) if (!depth[e[i].to])
dfs(e[i].to, u);
return;
}
void init(){
for (int i=1; i<=n; i++) lg[i] = lg[i-1] + (1<<lg[i-1]==i);
pow2[0] = 1;
for (int i=1; i<=28; i++) pow2[i] = 2*pow2[i-1];
dfs(1, 0);
for (int k=1; k<=lg[n]-1; k++) for (int i=1; i<=n; i++)
dp[i][k] = dp[dp[i][k-1]][k-1];
return;
}
inline void AddEdge(int u, int v){
tot++;
e[tot].to = v, e[tot].next = head[u];
head[u] = tot;
return;
}
inline int read(){
int x=0; char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9'){
x = x*10 + ch-'0';
ch=getchar();
}
return x;
}
int main(){
int u, v, last = 0, x, k, l, r;
n = read(), m = read();
for (int i=1; i<=n; i++) val[i] = read();
for (int i=1; i<n; i++){
u = read(), v = read();
AddEdge(u, v); AddEdge(v, u);
}
init();
bfs();
tree[0].left = tree[0].right = tree[0].val = 0;
top = 0; root[0] = 0;
for (int i=1; i<=n; i++){
root[i] = add(root[i-1], 1, n, val[BFS[i]]);
}
for (int i=1; i<=m; i++){
x = (read()^last)%n+1, k = read();
if (k>depth[x]-1){
puts("?");
continue;
}
l = src1(1, mp1[x], k), r = src2(mp1[x], n, k);
int tmp = search(root[l-1], root[r], 1, n, k);
if (tmp==-1){
puts("?");
continue;
}
last = tmp;
printf ("%d\n", last);
}
return 0;
}
0 条评论