HNOI2015 接水果-白红宇

强烈建议你试试无所不能的chatGPT，快点击我

HNOI2015 接水果

阅读量：6474 次

发布时间：2019-06-23

本文共 2365 字，大约阅读时间需要 7 分钟。

Description

Input

Output

Sample Input

10 10 10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 3 2 217394434 10 7 13022269 6 7 283254485 6 8 333042360 4 6 442139372 8 3 225045590 10 4 922205209 10 8 808296330 9 2 486331361 4 9 551176338  1 8 5 3 8 3 3 8 4 1 8 3 4 8 1 2 3 1 2 3 1 2 3 1 2 4 1 1 4 1

Sample Output

442139372 333042360 442139372 283254485 283254485 217394434 217394434 217394434 217394434 217394434

Data Constraint

我们考每个盘子对水果的影响。

每个盘子的路径，我们分两种情况讨论

1.a和b不构成祖先关系

那么它能影响的水果必须是起点在a或a的子树，终点在b或b的子树（起终点可调换）

2.a和b构成祖先关系

那么起点必须在b或b的子树，终点在c的子树之外。

我们发现满足要求的起点或终点在dfs序中都是一段连续的区间

我们以起点为x轴，终点为y轴，建一个坐标系，我们发现每个盘子对点的要求都可以用一个矩形来表示，每个查询只是查询一点，查询包含它的权值第k小的矩形

我们可以用经典的扫描线问题来解决。

对于y轴，开一个树状数组套权值线段树，支持区间修改和点查询。

问题解决，时间复杂度O(Nlog2N)

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           using namespace std;map
            
              H;struct plt{ int x,z,q;}a[40011],ask[40011];struct rec{ int x,l,r,k,q,id;}d[400011];struct tree{ int ls,rs,q;}tr[32000001];int ans[40011],g[40011],next[80011],y[80011],dfn[80011],size[80011];int fa[40011][16],que[40011],num[40011],root[40011],dep[40011];int T,tc,tot,ts,t,n,m,q,i,x,z,j,tt;void star(int i,int j){ tt++; next[tt]=g[i]; g[i]=tt; y[tt]=j;}bool cmp(rec a,rec b){ if(a.x==b.x)return a.k
             
              r||x>y)return; T++; d[T].x=l;d[T].l=x;d[T].r=y;d[T].k=0;d[T].q=q; T++; d[T].x=r;d[T].l=x;d[T].r=y;d[T].k=2;d[T].q=q; T++; d[T].x=x;d[T].l=l;d[T].r=r;d[T].k=0;d[T].q=q; T++; d[T].x=y;d[T].l=l;d[T].r=r;d[T].k=2;d[T].q=q;}void addrec(int x,int z,int q){ int j,k; if(dep[x]>dep[z])swap(x,z); if(dfn[z]>=dfn[x]&&dfn[z]
              
               mid)Insert(tr[t].rs,mid+1,r,x,y); tr[t].q=tr[tr[t].ls].q+tr[tr[t].rs].q;}void Ins(int l,int r,int y,int z){ while(r){ Insert(root[r],1,tot,y,z); r-=lowbit(r); } l--; while(l){ Insert(root[l],1,tot,y,-z); l-=lowbit(l); }}int Find(int l,int r,int k){ if(l==r)return num[l]; int mid,i,chk; chk=0; mid=(l+r)/2; for(i=1;i<=ts;i++)chk+=tr[tr[que[i]].ls].q; if(chk>=k){ for(i=1;i<=ts;i++)que[i]=tr[que[i]].ls; return Find(l,mid,k); } else{ for(i=1;i<=ts;i++)que[i]=tr[que[i]].rs; return Find(mid+1,r,k-chk); }}int Ask(int x,int z){ ts=0; while(x<=n){ que[++ts]=root[x]; x+=lowbit(x); } return Find(1,tot,z);}int main(){ scanf("%d%d%d",&n,&m,&q); for(i=1;i

转载于:https://www.cnblogs.com/applejxt/p/4450625.html

你可能感兴趣的文章

MongoDB--CSharp Driver Quickstart .

#pragma mark 添加分割线及其它类似标记 - 转

遗传算法实现自动组卷、随机抽题（转）

二分法求平方根（Python实现）

使用startActivityForResult方法（转）

so在genymotation中错误问题

Visual Studio 原生开发的10个调试技巧（二）

Windows内核再次出现0Day漏洞影响win2000到win10所有版本反病毒软件恐成瞎子

H3C品牌刀片系统强势首发

激励着我前进

我的友情链接

npm打包指定本地nexus仓库

LDAP服务原理详解

Docker容器初体验

[ComandDetail] Vim

delphi的加密与解密

第3部分管理NTFS权限

我的友情链接

面试总结之-查找算法分析

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2025-01-18 08:36:25 当前IP: 18.216.32.251 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我