树套树专题——bzoj 3110: [Zjoi2013] K大数查询 & 3236 [Ahoi2013] 作业 题解「建议收藏」

树套树专题——bzoj 3110: [Zjoi2013] K大数查询 & 3236 [Ahoi2013] 作业 题解

大家好,又见面了,我是全栈君。

【原题1】

3110: [Zjoi2013]K大数查询

Time Limit: 20 Sec  
Memory Limit: 512 MB


Submit: 978  
Solved: 476


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 c

Output

输出每一个询问的结果

Sample Input

2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3

Sample Output


1
2
1

HINT

N,M<=50000,N,M<=50000

a<=b<=N

1操作中abs(c)<=N

2操作中abs(c)<=Maxlongint

【传送门】感谢这位大牛给我的启示。

http://www.cnblogs.com/lazycal/archive/2013/08/05/3239304.html

【分析】一直听到过有一种奇妙的数据结构——树套树。

于是通过这道题我開始接触这样的算法。

树套树的本质就是两棵树套在一起(一般最外层的都是线段树)。对于当前的这棵树的每一个结点能够再开一棵树来维护。由于会爆内存,所以注意要动态开结点。说起来有点玄乎,先看看这道题吧。

我们能够先开一颗权值线段树。对于当前结点K,表示了权值范围为a~b的全部结点的信息。可是有人要问:这样怎么控制位置范围是l~r这个要求呢?我们能够在这个点上再开一棵树套树专题——bzoj 3110: [Zjoi2013] K大数查询 &amp; 3236 [Ahoi2013] 作业 题解「建议收藏」表示位置的信息。那么在第二重树中的结点sum[k]表示在a~b的权值范围内,位置范围是l~r的点的个数。查找的时候是BST原理。

【代码】(第一次写树套树。所以大部分借鉴了那个大牛。事实上还是比較好理解的O(∩_∩)O~~)

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=50000+5;
const int M=N*16*16;
int root[N*4],n,m,sum[M],left[M],right[M],lazy[M],c,L,R,cnt,i,opt;
inline int Read()
{
  char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar());
  int x=0;for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
  return x;
}
void put(int &k,int l,int r)
{
  if (!k) k=++cnt;
  if (L<=l&&r<=R) {lazy[k]++;sum[k]+=(r-l+1);return;}
  int mid=(l+r)/2;
  if (L<=mid) put(left[k],l,mid);
  if (R>mid) put(right[k],mid+1,r);
  sum[k]=sum[left[k]]+sum[right[k]]+lazy[k]*(r-l+1);
}
void update(int now,int l,int r)
{
  put(root[now],1,n);
  if (l==r) return;int mid=(l+r)/2;
  if (c<=mid) update(now*2,l,mid);
  else update(now*2+1,mid+1,r);
}
int calc(int k,int l,int r)
{
  if (!k) return 0;
  if (L<=l&&r<=R) return sum[k];
  int mid=(l+r)/2,temp=0;
  if (L<=mid) temp+=calc(left[k],l,mid);
  if (R>mid) temp+=calc(right[k],mid+1,r);
  return temp+lazy[k]*(min(R,r)-max(L,l)+1);
}
int ask(int now,int l,int r)
{
  if (l==r) return l;
  int mid=(l+r)/2,temp=calc(root[now*2],1,n);
  if (c<=temp) return ask(now*2,l,mid);
  c-=temp;return ask(now*2+1,mid+1,r);
}
int main()
{
  n=Read();m=Read();
  for (i=1;i<=m;i++)
  {
    opt=Read();L=Read();R=Read();c=Read();
    if (opt==1) c=n-c+1,update(1,1,n);
    else printf("%d\n",n-ask(1,1,n)+1);
  }
  return 0;
}

【原题】

3236: [Ahoi2013]作业

Time Limit: 100 Sec  
Memory Limit: 512 MB


Submit: 533  
Solved: 225


Description

树套树专题——bzoj 3110: [Zjoi2013] K大数查询 &amp; 3236 [Ahoi2013] 作业 题解「建议收藏」

Input

树套树专题——bzoj 3110: [Zjoi2013] K大数查询 &amp; 3236 [Ahoi2013] 作业 题解「建议收藏」

Output

树套树专题——bzoj 3110: [Zjoi2013] K大数查询 &amp; 3236 [Ahoi2013] 作业 题解「建议收藏」

Sample Input

3 4
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3

Sample Output

2 2
1 1
3 2
2 1

HINT


N=100000,M=1000000

【分析】这道题想熟练一下树套树。果断自己码代码。

第一问似乎比前面一题更加简单,由于连lazy操作都不用,仅仅要单点查询,区间询问就可以。

第二问真是费脑筋。想写树套树也没什么事,可惜想法会复杂的多,像我这样的刚開始学习的人还是算了~~那怎么办呢?我又想到了莫队算法!首先对于l,r,依照莫队对它排序一下。由于要处理a~b的权值范围,我们还要用树状数组来维护单点改动和区间询问。

【代码1】

#include<cstdio>
#include<algorithm>
#include<cmath>
#define LL(x) (x&-x)
#define N 100005
#define M 17*17*N
#define Q 1000005
using namespace std;
int n,m,i,cnt,x,y,L,R,s,l,r,t1,t2,Num,ans;
int sum[M],left[M],right[M],root[N*3],data[N],pos[N],ans1[Q],ans2[Q],f[N],flag[N];
struct HHD{int l,r,id,x,y;}a[Q];
bool cmp(HHD a,HHD b)
{
  if (pos[a.l]!=pos[b.l]) return a.l<b.l;
  if (pos[a.l]&1) return a.r<b.r;else return a.r>b.r;
}
inline int Read()
{
  char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar());
  int x=0;for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
  return x;
}
void tree(int &k,int l,int r)
{
  if (!k) k=++cnt;sum[k]++;
  if (l==r) return;int mid=(l+r)>>1;
  if (i<=mid) tree(left[k],l,mid);
  else tree(right[k],mid+1,r);
}
void update(int k,int l,int r)
{
  while (l!=r)
  {
    tree(root[k],1,n);
    int mid=(l+r)>>1;
    if (data[i]<=mid) r=mid,k*=2;
    else l=mid+1,k=k*2+1;
  }
  tree(root[k],1,n);
}
int calc(int k,int l,int r)
{
  if (L<=l&&r<=R||!k) return sum[k];
  int mid=(l+r)>>1,o=0;
  if (L<=mid) o+=calc(left[k],l,mid);
  if (R>mid) o+=calc(right[k],mid+1,r);
  return o;
}
int ask(int k,int l,int r)
{
  if (x<=l&&r<=y) return calc(root[k],1,n);
  if (!root[k]) return 0;
  int mid=(l+r)>>1,o=0;
  if (x<=mid) o+=ask(k*2,l,mid);
  if (y>mid) o+=ask(k*2+1,mid+1,r);
  return o;
}
inline void add(int x,int c){for (;x<=n;x+=LL(x)) f[x]+=c;}
inline int Sum(int x){int o=0;for (;x;x-=LL(x)) o+=f[x];return o;}
int main()
{
  freopen("3236.in","r",stdin);
  freopen("3236.out","w",stdout);
  n=Read();m=Read();
  for (i=1;i<=n;i++)
    data[i]=Read(),update(1,1,n);
  s=int(sqrt(n));
  for (i=1;i<=n;i++) pos[i]=i/s+1;
  for (i=1;i<=m;i++)
  {
    L=Read(),R=Read(),x=Read(),y=Read();
    a[i].l=L;a[i].r=R;a[i].x=x;a[i].y=y;a[i].id=i;
    ans1[i]=ask(1,1,n);
  }
  sort(a+1,a+m+1,cmp);
  l=1;r=1;flag[data[1]]=1;add(data[1],1);
  for (i=1;i<=m;i++)
  {
    while (r<a[i].r) {flag[data[++r]]++;if (flag[data[r]]==1) add(data[r],1);}
    while (l>a[i].l) {flag[data[--l]]++;if (flag[data[l]]==1) add(data[l],1);}
    while (r>a[i].r) {flag[data[r]]--;if (!flag[data[r]]) add(data[r],-1);r--;}
    while (l<a[i].l) {flag[data[l]]--;if (!flag[data[l]]) add(data[l],-1);l++;}
    ans2[a[i].id]=Sum(a[i].y)-Sum(a[i].x-1);
  }
  for (i=1;i<=m;i++)
    printf("%d %d\n",ans1[i],ans2[i]);
  return 0;
}

【超时!】底下測70s。交上去就T了。

哎!这么办呢?通过调试,我发现树套树M*LOG(N)^2的时间效率还是莫队的M*LOG(N)*SQRT(N)的效率快!

!于是忍痛割爱把树套树也改成了莫队,然后底下40s,交上去60s过了。

【代码2】

#include<cstdio>
#include<algorithm>
#include<cmath>
#define LL(x) (x&-x)
#define N 100005
#define Q 1000005
using namespace std;
int n,m,i,cnt,x,y,L,R,s,l,r,t1,t2,Num,ans;
int data[N],pos[N],ans1[Q],ans2[Q],f[N],flag[N],g[N];
struct HHD{int l,r,id,x,y;}a[Q];
bool cmp(HHD a,HHD b)
{
  if (pos[a.l]!=pos[b.l]) return a.l<b.l;
  if (pos[a.l]&1) return a.r<b.r;else return a.r>b.r;
}
inline int Read()
{
  char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar());
  int x=0;for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
  return x;
}
inline void add(int x,int c){for (;x<=n;x+=LL(x)) f[x]+=c;}
inline int Sum(int x){int o=0;for (;x;x-=LL(x)) o+=f[x];return o;}
inline void add2(int x,int c){for (;x<=n;x+=LL(x)) g[x]+=c;}
inline int Sum2(int x){int o=0;for (;x;x-=LL(x)) o+=g[x];return o;}
int main()
{
  n=Read();m=Read();
  for (i=1;i<=n;i++)
    data[i]=Read();
  s=int(sqrt(n));
  for (i=1;i<=n;i++) pos[i]=i/s+1;
  for (i=1;i<=m;i++)
  {
    L=Read(),R=Read(),x=Read(),y=Read();
    a[i].l=L;a[i].r=R;a[i].x=x;a[i].y=y;a[i].id=i;
  }
  sort(a+1,a+m+1,cmp);
  l=1;r=1;flag[data[1]]=1;add(data[1],1);add2(data[1],1);
  for (i=1;i<=m;i++)
  {
    while (r<a[i].r) {flag[data[++r]]++;if (flag[data[r]]==1) add(data[r],1);add2(data[r],1);}
    while (l>a[i].l) {flag[data[--l]]++;if (flag[data[l]]==1) add(data[l],1);add2(data[l],1);}
    while (r>a[i].r) {flag[data[r]]--;if (!flag[data[r]]) add(data[r],-1);add2(data[r],-1);r--;}
    while (l<a[i].l) {flag[data[l]]--;if (!flag[data[l]]) add(data[l],-1);add2(data[l],-1);l++;}
    ans2[a[i].id]=Sum(a[i].y)-Sum(a[i].x-1);
    ans1[a[i].id]=Sum2(a[i].y)-Sum2(a[i].x-1);
  }
  for (i=1;i<=m;i++)
    printf("%d %d\n",ans1[i],ans2[i]);
  return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115464.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 如何注册免费域名

    如何注册免费域名首先,你需要一个域名,如果你自己买的有域名,那么这里我再说就没太多意义了,这里要说的是用免费的域名,是的,你没有看错,免费的域名首先登陆https://my.freenom.com网站注册个用户,当然了也可以先不用注册,如果想跟着本教程走,则最好是先不要注册用户(有Google账户的小伙伴可以直接登陆了)然后就是想个你要注册的域名,搜一下(注:只有.tk、.cf、.ml、.ga、….

  • 简单的webService实例

    简单的webService实例本文主要是描述了一个简单的webservice发布服务的过程,与怎么去测试该发布的服务的过程

  • Python 学习笔记 变量 xxx XXX「建议收藏」

    Python 学习笔记 变量 xxx XXX「建议收藏」Python学习笔记变量xxxXXXname=”adalovelace”print(name.title())print(name.upper())print(name.lower())first_name=”ada”last_name=”lovelace”full_name=first_name+””+last_nameprint(full_name)print(“Hello,”+…

  • 实现KMO和Bartlett的球形度检验的两种方法[通俗易懂]

    实现KMO和Bartlett的球形度检验的两种方法[通俗易懂]文章目录实现KMO和Bartlett的球形度检验的两种方法SPSS实现KMO和Bartlett的球形度检验第一步:选择“因子分析”第二步:选择变量第三步:选择KMO和巴特利特球形度检验输出结果SAS实现KMO和Bartlett的球形度检验数据集来源参考资料实现KMO和Bartlett的球形度检验的两种方法SPSS实现KMO和Bartlett的球形度检验第一步:选择“因子分析”导入数据…

  • mtk手机维修_mtk平台手机

    mtk手机维修_mtk平台手机默认分类2009-10-1902:21:04阅读1252评论7字号:大中小  MTK用电池不开机,用外用电源能开机的维修方法:MTK用电池不开机,用外用电源能开机的维修方法,我们可以找到VBAT也就是电触B+通电源的sas31233l213321+987+9877777777777777777777777777777777777777777777777777

    2022年10月28日
  • Pytest(6)重复运行用例pytest-repeat

    Pytest(6)重复运行用例pytest-repeat前言平常在做功能测试的时候,经常会遇到某个模块不稳定,偶然会出现一些bug,对于这种问题我们会针对此用例反复执行多次,最终复现出问题来。自动化运行用例时候,也会出现偶然的bug,可以针对单个用例,

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号