bzoj3110 k大数查询 zjoi2013
发布时间:2020-12-14 02:46:50 所属栏目:大数据 来源:网络整理
导读:树套树。 在一个区间里面求另一个区间的值 本来第一反应是treap套线段树 ? 后来发现代码难度对我比较高 ?orz 果断改成外层权值线段树 ?套 ?内层区间线段树 内层空间硬开开不下。。 只好先按着内存上限开了 然后用一个变量记录某个点对应的内层线段树节点 实
树套树。 在一个区间里面求另一个区间的值 本来第一反应是treap套线段树 ? 后来发现代码难度对我比较高 ?orz 果断改成外层权值线段树 ?套 ?内层区间线段树 内层空间硬开开不下。。 只好先按着内存上限开了 然后用一个变量记录某个点对应的内层线段树节点 实现一个伪指针 内层的lazy加上永久标记比较快(^o^)/~ #include <cstdio> #define L(i,j,k) for(int i = j;i <= k;i++) #define LL long long int n,m,op,a,b,tmp1; LL c,cnt; struct point { int ch[2]; int l,r; int x,lazy; }use[9999999]; int t[200003]; void insert_i (int u,int L,int R) { if(use[u].l == L && R == use[u].r) { use[u].lazy++; use[u].x +=R - L + 1; return; } int mid = (use[u].l + use[u].r) / 2; if(L > mid) { if(!use[u].ch[1]) use[u].ch[1] = ++cnt; if(use[use[u].ch[1]].l == 0) { use[use[u].ch[1]].l = mid + 1; use[use[u].ch[1]].r = use[u].r; } insert_i(use[u].ch[1],L,R); } else { if(R <= mid) { if(!use[u].ch[0]) use[u].ch[0] = ++cnt; if(use[use[u].ch[0]].l == 0) { use[use[u].ch[0]].l = use[u].l; use[use[u].ch[0]].r = mid; } insert_i(use[u].ch[0],R); } else { if(!use[u].ch[1]) use[u].ch[1] = ++cnt; if(!use[u].ch[0]) use[u].ch[0] = ++cnt; if(use[use[u].ch[0]].l == 0) { use[use[u].ch[0]].l = use[u].l; use[use[u].ch[0]].r = mid; } if(use[use[u].ch[1]].l == 0) { use[use[u].ch[1]].l = mid + 1; use[use[u].ch[1]].r = use[u].r; } insert_i(use[u].ch[0],mid); insert_i(use[u].ch[1],mid + 1,R); } } use[u].x += R - L + 1; } void insert_o (int u,int l,int r) { if(l != r) { int mid = (l + r) / 2; if(c <= mid) insert_o(u << 1,l,mid); else insert_o(u << 1 | 1,r); } if(!t[u]) t[u] = ++cnt; if(use[t[u]].l == 0) { use[t[u]].l = 1; use[t[u]].r = 50000; } insert_i(t[u],b); } int search (int u,int r,int R,int lz) { if(l == L && r == R) return lz * (r - l + 1) + use[u].x; int mid = (l + r) / 2; if(L > mid) return search(use[u].ch[1],r,R,lz + use[u].lazy); else { if(R <= mid) return search(use[u].ch[0],mid,lz + use[u].lazy); return search(use[u].ch[0],lz + use[u].lazy) + search(use[u].ch[1],lz + use[u].lazy); } } int find (int u,int rest) { if(l == r) return l; int lc = (u << 1); int rc = (u << 1 | 1); if((tmp1 = search(t[rc],1,50000,0) + rest ) < c) return find(lc,(l + r) / 2,tmp1); return find(rc,(l + r) / 2 + 1,rest); } int main () { scanf("%d%d",&n,&m); L(i,m) if((scanf("%d%d%d%d",&op,&a,&b,&c),op) == 1) insert_o(1,50000); else printf("%dn",find(1,0)); } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |