【BZOJ3110】【codevs1616】K大数查询,权值线段树套普通线段树
Time:2016.05.09 传送门1 #include<bits/stdc++.h>
#define M 50005
#define ul unsigned int
using namespace std;
int n,m,cnt_S,cnt_V,root_S[M<<4],root_V;
struct Segment_tree
{
ul sum,lazy;
int ch[2];
}S[M*300];
struct Value_tree
{
int ch[2];
}V[M];
int in()
{
int t=0,f=1;char ch=getchar();
while (!isdigit(ch))
{
if (ch=='-') f=-1;
ch=getchar();
}
while (isdigit(ch)) t=(t<<3)+(t<<1)+ch-48,ch=getchar();
return f*t;
}
void S_change(int &rt,int begin,int end,int l,int r)
{
if (!rt) rt=++cnt_S;
if (l<=begin&&end<=r)
{
S[rt].sum+=end-begin+1;
S[rt].lazy++;
return;
}
int mid=begin+end>>1;
if (mid>=l) S_change(S[rt].ch[0],begin,mid,l,r);
if (mid<r) S_change(S[rt].ch[1],mid+1,end,r);
S[rt].sum=S[S[rt].ch[0]].sum+S[S[rt].ch[1]].sum+S[rt].lazy*(end-begin+1);
}
ul S_get(int &rt,int r)
{
if (!rt) return 0;
if (l<=begin&&end<=r) return S[rt].sum;
int mid=begin+end>>1;ul ans=S[rt].lazy*(min(r,end)-max(l,begin)+1);
if (mid>=l) ans+=S_get(S[rt].ch[0],r);
if (mid<r) ans+=S_get(S[rt].ch[1],r);
return ans;
}
void V_change(int &rt,int x,int y,int z)
{
if (!rt) rt=++cnt_V;
S_change(root_S[rt],1,n,x,y);
if (begin==end) return;
int mid=begin+end>>1;
if (mid>=z)
V_change(V[rt].ch[0],y,z);
else
V_change(V[rt].ch[1],z);
}
int V_get(int rt,int z)
{
if (begin==end) return end;
int mid=begin+end>>1;
ul t=S_get(root_S[V[rt].ch[1]],y);
if (z<=t)
return V_get(V[rt].ch[1],z);
else
return V_get(V[rt].ch[0],z-t);
}
main()
{
n=in();m=in();
int opt,z;
while (m--)
{
opt=in();x=in();
y=in();z=in();
if (opt==1) V_change(root_V,z);
else printf("%lun",V_get(root_V,z));
}
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |