BZOJ3110: [Zjoi2013]K大数查询
发布时间:2020-12-24 07:30:45 所属栏目:大数据 来源:网络整理
导读:Description 有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c 如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。 Input 第一行N,M 接下来M行,每行形如1 a b c或2 a b
Description有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c Input第一行N,M接下来M行,每行形如1 a b c或2 a b c Output输出每个询问的结果Sample Input2 51 1 2 1 1 1 2 2 2 1 1 2 2 1 1 1 2 1 2 3 Sample Output12 1 HINT
N,M<=50000,N,M<=50000 Source第一次写树套树 本题有整体二分写法,但强行当成树套树题练习 注意50000*50000会爆int,改成unsigned int即可#include <bits/stdc++.h> using namespace std; typedef unsigned int Int; inline Int read() { Int sc = 0,f = 1; char ch = getchar(); while( ch < '0' || ch > '9' ) { if( ch == '-') f = -1; ch = getchar(); } while( ch >= '0' && ch <= '9' ) sc = sc * 10 + ch - '0',ch = getchar(); return sc * f; } const Int MAXN = 50050; const Int MAXM = MAXN << 8; Int n,m,L,R,c,tag[MAXM],root[MAXN << 2],cnt,sum[MAXM],ls[MAXM],rs[MAXM]; inline void modify(Int &x,Int l,Int r,Int ql,Int qr,Int v) { if( !x ) x = ++cnt; if( l == ql && r == qr ) { sum[ x ] += r - l + 1; tag[ x ]++; return ; } Int mid = l + r >> 1; if( qr <= mid ) modify( ls[ x ],l,mid,ql,qr,v ); else if( ql > mid ) modify( rs[ x ],mid + 1,r,v ); else modify( ls[ x ],v ),modify( rs[ x ],v ); sum[ x ] = sum[ ls[ x ] ] + sum[ rs[ x ] ] + tag[ x ] * ( r - l + 1 ); } inline void update() { Int l = 1,r = n,x = 1; while( l < r ) { modify( root[ x ],1,n,c ); Int mid = l + r >> 1; if( c <= mid ) r = mid,x <<= 1; else l = mid + 1,( x <<= 1 ) |= 1; } modify( root[ x ],c ); } inline Int get(Int x,Int qr) { if( l == ql && r == qr ) return sum[ x ]; Int mid = l + r >> 1,ans = ( min( qr,r ) - max( ql,l ) + 1 ) * tag[ x ]; if( qr <= mid ) return get( ls[ x ],qr ) + ans; if( ql > mid ) return get( rs[ x ],qr ) + ans; return get( ls[ x ],mid ) + get( rs[ x ],qr ) + ans; } inline Int query() { Int l = 1,x = 1; while( l < r ) { int mid = l + r >> 1,tmp; if( ( tmp = get( root[ x << 1 ],R ) ) >= c ) r = mid,( x <<= 1 ) |= 1,c -= tmp; } return l; } int main() { n = read(),m = read(); while( m-- ) { Int opt = read(); L = read(),R = read(),c = read(); if( opt == 1 ) c = n - c + 1,update(); else printf( "%dn",n - query() + 1 ); } } (编辑:上饶站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |