网站建设方案网站安全,php律师网站源码,剪辑培训班一般学费多少,科技类公司网站怎么设计题意#xff1a;多次询问#xff0c;每次询问某区间的第k小数。
可持久化线段树#xff1a;
掺杂了一点前缀和的思想#xff0c;对于每一个1 ~ i 的区间都建一个树#xff0c;每个节点存的都是一个线段树#xff0c;值存的是当前区间中初始数组按大小排序后[l, r]之间的… 题意多次询问每次询问某区间的第k小数。
可持久化线段树
掺杂了一点前缀和的思想对于每一个1 ~ i 的区间都建一个树每个节点存的都是一个线段树值存的是当前区间中初始数组按大小排序后[l, r]之间的数的个数这个lr指的是每个节点的左右端点。如果想求[l, r]区间内的第k小数只需要同时遍历[1l - 1] 以及 [1, r] 两个版本的线段树因为即使版本不同线段树的结构是不变的所以可以发现如果某个节点区间在老版本里面已经出现了x个数那么在新版本中的当前区间需要减去x这样才是我们所求的区间里面数的数量通过查找第k个数的位置找到第k小的数是哪个。
有点乱直接看代码吧。 using namespace std;
typedef long long ll;
typedef pairint, int pii;
typedef pairint, string pis;
const int mod 1e9 7;
const int N 2e6 10;
int dx[] {-1, 0, 1, 0, -1, 1, 1, -1};
int dy[] {0, 1, 0, -1, 1, 1, -1, -1};
int n, m, idx;
int o[N], root[N];
struct node{int l, r;int cnt;
}tr[N];
vectorint nums;int find(int x){//找到对应的离散值return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}int build(int l, int r){// 建树int p idx;// 给当前节点分配序号if(l r) return p;// 区间不可再分直接返回当前节点序号即可int mid l r 1; // 找到区间的中点tr[p].l build(l, mid), tr[p].r build(mid 1, r);// 分别对左右儿子进行建树return p;// 将当前树的序号返回
}int insert(int p, int l, int r, int x){// 插入某个元素p为上一个版本的当前区间的树序号int q idx;// 为当前子树分配序号tr[q] tr[p]; // 继承老版本中当前子树的信息if(l r) {// 需要修改的就是当前位置将cnt加一即可tr[q].cnt ;return q;}int mid l r 1;if(x mid) tr[q].l insert(tr[p].l, l, mid, x);// 需要插入得位置在左儿子else tr[q].r insert(tr[p].r, mid 1, r, x);// 在右儿子tr[q].cnt tr[tr[q].l].cnt tr[tr[q].r].cnt; // 更新当前版本的当前区间的cnt状态return q;//返回当前的序号
}int query(int q, int p, int l, int r, int k){// 查询lr区间的第k小数q为当前版本p为老版本if(l r) return r; // 找到所查元素int cnt tr[tr[q].l].cnt - tr[tr[p].l].cnt;// 通过新老版本的差可以得出当前区间的真实数量int mid l r 1;if(k cnt) return query(tr[q].l, tr[p].l, l, mid, k);// 再左儿子查左儿子更新新老版本的左儿子树的序号else return query(tr[q].r, tr[p].r, mid 1, r, k - cnt);// 更新右儿子树的序号以及新的k的状态
}inline void sovle() {cin n m;for(int i 1; i n; i ){cin o[i];nums.push_back(o[i]);}sort(nums.begin(), nums.end());nums.erase(unique(nums.begin(), nums.end()), nums.end());//以上都是在进行离散化操作root[0] build(0, nums.size() - 1);// 建立一个空的线段树用于下一次操作继承哨兵作用for(int i 1; i n; i ) // 没差一次就建立一个新版本的树root[i] insert(root[i - 1], 0, nums.size() - 1, find(o[i]));while(m --){int l, r, k;cin l r k;int i query(root[r], root[l - 1], 0, nums.size() - 1, k);//查询操作cout nums[i] endl; }
}signed main(void) {IOS;int t 1;
// cin t;while(t --) sovle();return 0;
}
