[ZJOI 2013] bzoj3110 K大数查询 【树套树】
发布时间：2021-01-16 22:03:10 所属栏目：大数据 来源：网络整理
导读：副标题#e# Description 有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c 如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。 Input 第一行N，M 接下来M行，每行形如1 a
#include <cstdio>
const int Maxn = 50000 + 10,MS = Maxn << 8;
int root[Maxn << 2],ls[MS],rs[MS],tot,M;
long long Cnt[MS],ly[MS];
//线段树的外层为权值，内层为区间
int Ina; char Inc; bool InSign;
inline int geti()
{
InSign = 0;
while (Inc = getchar(),Inc < '0' || Inc > '9') InSign |= Inc == '-';
Ina = Inc - '0';
while (Inc = getchar(),Inc >= '0' && Inc <= '9') Ina = (Ina << 3) + (Ina << 1) + Inc - '0';
if (InSign) Ina = -Ina;
return Ina;
}
void Insert(int &u,int x,int y) { //内层线段树
if (!u) u = ++tot;
if (l >= x && r <= y) {
Cnt[u] += r - l + 1;
++ly[u];//永久化懒惰标记
return;
}
int mid = (l + r) >> 1;
if (y <= mid) Insert(ls[u],x,y);
else if (x > mid) Insert(rs[u],mid + 1,y);
else {
Insert(ls[u],mid);
Insert(rs[u],y);
}
Cnt[u] += y - x + 1;
}
void add(int x,int y,int val) { //外层线段树 权值线段树
int l = 1,r = N,u = 1,mid;
while (true) {
Insert(root[u],y);//
if (l == r) break; //边界
mid = (l + r) >> 1; u <<= 1;
if (val <= mid) r = mid;
else l = mid + 1,u |= 1;
}
}
long long Count(int u,int y) {
if (l >= x && r <= y) return Cnt[u];
int mid = (l + r) >> 1; long long ans = 0;
if (y <= mid) ans = Count(ls[u],y);
else if (x > mid) ans = Count(rs[u],y);
else ans = Count(ls[u],mid) + Count(rs[u],y);
ans += (y - x + 1) * ly[u];
return ans;
}
int query(int x,long long val) {
int l = 1,u = 1; long long tmp;
while (true) {
if (l == r) return l;
mid = (l + r) >> 1;
tmp = Count(root[u << 1 | 1],y);
if (tmp >= val) l = mid + 1,u = u << 1 | 1;
else r = mid,u = u << 1,val -= tmp;
}
}
int main() {
N = geti(),M = geti();
int type,b; long long c;
while (M--) {
type = geti(),a = geti(),b = geti(),c = geti();
if (type < 2) add(a,c);
else printf("%dn",query(a,c));
}
return 0;
}
好像还有其他做法。。暂时先贴这个。。什么CDQ分治整体二分我有空再去看qwq 我的代码比较丑=。= #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
int Ina; char Inc; bool InSign;
inline int read()
{
InSign = 0;
while (Inc = getchar(),Inc >= '0' && Inc <= '9') Ina = (Ina << 3) + (Ina << 1) + Inc - '0';
if (InSign) Ina = -Ina;
return Ina;
}
int n,m;
const int Maxn = 50000 + 10,tot;
long long cnt[MS],ly[MS];
//线段树的外层为权值，内层为区间
void insert(int& u,int y)
{
if(!u)u = ++tot;
if(l>=x&&r<=y){ cnt[u] += r-l+1;++ly[u];return;}
int mid = (l+r)>>1;
if(y<=mid)insert(ls[u],y);
else if(x>mid)insert(rs[u],y);
else
{
insert(ls[u],mid);
insert(rs[u],y);
}
cnt[u] += y - x + 1;
}
/*
void add(int x,LL v)
{
insert(root[u] ? root[u] : root[u] = ++size,n,R);
if(l==r) return;
int mid = (l+r)>>1;
if(x<=mid)add(u<<1,x);
else add(u<<1|1,x);
}
*/
void add(int x,int v)
{
int l=1,r=n,u=1,mid;
while(true)
{
insert(root[u],y);
if(l==r)break;
mid = (l+r)>>1;u<<=1;
if(v<=mid)r = mid;
else l = mid+1,u|=1;
}
}
LL Count(int u,int y)
{
if(l>=x&&r<=y)return cnt[u];
int mid = (l+r)>>1;LL ans = 0;
if(y<=mid)ans = Count(ls[u],y);
else if(x>mid)ans = Count(rs[u],y);
else ans = Count(ls[u],y);
ans += (y-x+1)*ly[u];//懒惰标记永久化了
return ans;
}
/*
递归版：
int query(int u,int x)
{ // 外层线段树
if(l == r) return l;
int mid = (l + r) >> 1;
int cnt = count(root[rch],R);
if(cnt >= x) return query(rch,x);
else return query(lch,x - cnt);
}
*/
int query(int x,LL v)
{
int l = 1,r = n,u = 1;LL tmp;
while(true)
{
if(l==r)return l;
mid = (l+r)>>1;
tmp = Count(root[u<<1|1],y);
if(tmp>=v)l=mid+1,u=u<<1|1;
else r=mid,u=u<<1,v-=tmp;
}
}
int main(void)
{
n = read(),m = read();
int type,b;LL c;
for(int i=1;i<=m;i++)
{
type = read(),a = read(),b = read(),c = read();
if(type == 1)add(a,c);
else printf("%dn",c));
}
return 0;
}
下面是其他解法。。 STL暴力大法 http://blog.csdn.net/qq_21110267/article/details/44514709 （编辑：徐州站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
