首页 / 更多教程 / K大数查询 HYSBZ - 3110

K大数查询 HYSBZ - 3110

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了K大数查询 HYSBZ - 3110，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4984字，纯文字阅读大概需要8分钟。

内容图文

K大数查询

HYSBZ - 3110

本来是刷整体二分的，被这个sb题折腾了一下午，用cin就RE, 用scanf就过了＝_=

收获就是偶然学到了树状数组区间修改区间查询的写法吧。。。

                      1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4usingnamespace std;
  5#define LL long long 
  6constint maxn = 1e5 + 10;
  7constint maxq = 5e4 + 10;
  8struct Qry{
  9int a, b;
 10    LL c;
 11int id;
 12     Qry(int a = 0, int b = 0, LL c = 0, int id = 0):
 13        a(a), b(b), c(c), id(id){}
 14}q[maxq], q1[maxq], q2[maxq];
 15 16 17struct Seg{
 18     LL sum[maxn<<2], add[maxn<<2];
 19void init(){
 20         memset(add, 0, sizeof add);
 21         memset(sum, 0, sizeof sum);
 22    }
 23void pushup(int rt){
 24         sum[rt] = sum[rt<<1] + sum[rt<<1|1];
 25    }
 26void pushdown(int rt, int m){
 27if(add[rt]){
 28             sum[rt<<1] += (m - (m>>1)) * add[rt];
 29             sum[rt<<1|1] += (m >> 1) * add[rt];
 30             add[rt<<1] += add[rt];
 31             add[rt<<1|1] += add[rt];
 32             add[rt] = 0;
 33        }
 34    }
 35 36void update(int L, int R, int v, int l, int r, int rt){
 37if(L <= l && r <= R){
 38             sum[rt] += v * (r - l + 1);
 39             add[rt] += v;
 40return;
 41        }
 42         pushdown(rt, r - l + 1);
 43int m = (l + r) >> 1;
 44if(L <= m) update(L, R, v, l, m, rt<<1);
 45if(R > m) update(L, R, v, m + 1, r, rt<<1|1);
 46        pushup(rt);
 47    }
 48 49     LL query(int L, int R, int l, int r, int rt){
 50if(L <= l && r <= R){
 51return sum[rt];
 52        }
 53         pushdown(rt, r - l + 1);
 54int m = (l + r) >> 1;
 55         LL res = 0;
 56if(L <= m) res += query(L, R, l, m, rt<<1);
 57if(R > m) res += query(L, R, m + 1, r, rt<<1|1);
 58return res;
 59    }
 60}seg;
 61int ans[maxq];
 62int n;
 63void solve(int L, int R, int l, int r){
 64if(L > R) return;
 65if(l == r){
 66for(int i = L; i <= R; i++){
 67if(q[i].id > 0) ans[q[i].id] = l;
 68        }
 69return;
 70    }
 71int m = (l + r) >> 1;
 72int f = 0, g = 0;
 73for(int i = L; i <= R; i++){
 74if(q[i].id < 0){
 75if(q[i].c <= m){
 76                 seg.update(q[i].a, q[i].b, 1, 1, n, 1);
 77                 q1[f++] = q[i];
 78             }else q2[g++] = q[i];
 79         }else{
 80             LL temp = seg.query(q[i].a, q[i].b, 1, n, 1);
 81if(temp >= q[i].c) q1[f++] = q[i];
 82else{
 83                 q[i].c -= temp;
 84                 q2[g++] = q[i];
 85            }
 86        }
 87    }
 88for(int i = 0; i < f; i++) if(q1[i].id < 0) seg.update(q1[i].a, q1[i].b, -1, 1, n, 1);
 89     memcpy(q + L, q1, f * sizeof(Qry));
 90     memcpy(q + L + f, q2, g * sizeof(Qry));
 91     solve(L, L + f - 1, l, m);
 92     solve(L + f, R, m + 1, r);
 93}
 94 95int main(){
 96int m;
 97while(scanf("%d %d", &n, &m) != EOF){
 98int op, a, b;
 99        LL c;
100        seg.init();
101int cnt = 0;
102for(int i = 1; i <= m; i++){
103             cin>>op>>a>>b>>c;
104if(op == 1){
105                 q[i] = Qry(a, b, n + 1LL - c, -1);
106             }else{
107                 q[i] = Qry(a, b, c, ++cnt);
108            }
109        }
110         solve(1, m, 1, n * 2LL + 1);
111for(int i = 1; i <= cnt; i++) printf("%d\n", n - ans[i] + 1);
112    }
113 }

线段树维护

                     1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4usingnamespace std;
 5#define LL long long 
 6constint maxn = 1e5 + 10;
 7constint maxq = 1e5 + 10;
 8struct Qry{
 9int a, b;
10    LL c;
11int id;
12     Qry(int a = 0, int b = 0, LL c = 0, int id = 0):
13        a(a), b(b), c(c), id(id){}
14}q[maxq], q1[maxq], q2[maxq];
15//树状数组区间修改区间求和 http://blog.csdn.net/blackjack_/article/details/7499747916struct Bit{
17int n;
18    LL c1[maxn], c2[maxn];
19void init(int _n){
20         n = _n;
21         memset(c1, 0, sizeof(c1));
22         memset(c2, 0, sizeof(c2));
23    }
24void add(int x,LL add){  
25for(int i=x;i<=n;i+=i&(-i)){  
26             c1[i]+=add;  
27             c2[i]+=x*add;  
28        }  
29    }  
30     LL sum(int x){  
31         LL ans=0;  
32for(int i=x;i>0;i-=i&(-i)){  
33             ans+=(x+1)*c1[i]-c2[i];  
34        }  
35return ans;  
36    } 
37}bit;
38int ans[maxq];
39int n;
40void solve(int L, int R, int l, int r){
41if(L > R) return;
42if(l == r){
43for(int i = L; i <= R; i++){
44if(q[i].id > 0) ans[q[i].id] = l;
45        }
46return;
47    }
48int m = (l + r) >> 1;
49int f = 0, g = 0;
50for(int i = L; i <= R; i++){
51if(q[i].id < 0){
52if(q[i].c <= m){
53                bit.add(q[i].a, 1LL);
54                 bit.add(q[i].b+1, -1LL);
55                 q1[f++] = q[i];
56             }else q2[g++] = q[i];
57         }else{
58             LL temp = bit.sum(q[i].b) - bit.sum(q[i].a - 1);
59if(temp >= q[i].c) q1[f++] = q[i];
60else{
61                 q[i].c -= temp;
62                 q2[g++] = q[i];
63            }
64        }
65    }
66for(int i = 0; i < f; i++) if(q1[i].id < 0 && q1[i].c <= m) {
67         bit.add(q1[i].a, -1);
68         bit.add(q1[i].b + 1, 1);
69    }
70     memcpy(q + L, q1, f * sizeof(Qry));
71     memcpy(q + L + f, q2, g * sizeof(Qry));
72     solve(L, L + f - 1, l, m);
73     solve(L + f, R, m + 1, r);
74}
7576int main(){
77int m;
78while(scanf("%d %d", &n, &m)!= EOF){
79int op, a, b;
80        LL c;
81        bit.init(n);
82int cnt = 0;
83for(int i = 1; i <= m; i++){
84             cin>>op>>a>>b>>c;
85if(op == 1){
86                 q[i] = Qry(a, b, n + 1LL - c, -1);
87             }else{
88                 q[i] = Qry(a, b, c, ++cnt);
89            }
90        }
91         solve(1, m, 1, n * 2LL + 1);
92for(int i = 1; i <= cnt; i++) printf("%d\n", n - ans[i] + 1);
93    }
94 }

树状数组维护

原文：https://www.cnblogs.com/yijiull/p/8324723.html

内容总结

以上是互联网集市为您收集整理的K大数查询 HYSBZ - 3110全部内容，希望文章能够帮你解决K大数查询 HYSBZ - 3110所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

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

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1226119.html

来源：【匿名】

【上一篇】用户及用户场景分析【下一篇】关于IE的RegExp.exec的问题

更多 ►

【K大数查询 HYSBZ - 3110】教程文章相关的互联网学习教程文章

sql sever 查询语句【代码】

参考https://blog.csdn.net/dacainiao007/article/details/8129637子查询：嵌套在其他查询中的查询称之。子查询又称内部，而包含子查询的语句称之外部查询（又称主查询）。所有的子查询可以分为两类，即相关子查询和非相关子查询 1. 非相关子查询是独立于外部查询的子查询，子查询总共执行一次，执行完毕后将值传递给外部查询。 2. 相关子查询的执行依赖于外部查询的数据，外部查询执行一行，子查询就执行一次。故非相关子查询比...

.NET应用架构设计—面向查询的领域驱动设计实践（调整传统三层架构，外加维护型的业务开关）

阅读目录：1.背景介绍2.在业务层中加入核心领域模型（引入DomainModel，让逻辑、数据有家可归，变成一个完整的业务对象）3.统一协调层Application Layer（加入协调层来转换DomianModel）4.从数据扁平结构转换成OO体系结构（使用OO丰富代码结构）5.DomainModel中的内容（带开关的Specification、SOA化的Specification）6.模式、重构、单元测试在领域模型中的运用1.背景介绍由于时间关系废话不多扯了，直奔主题，对领域驱动设计不是太...

DataTable查询数据集

1.查询后获取对应的数据集后，传递参数strcodeName，根据数据集中strcodeName的匹配对应字段，获取数据集中对应的目的字段private string GetStrName(DataTable dtable, string strcodeName) { string Name = strcodeName; DataRow[] dr = dtable.Select("匹配对应字段=" + strcodeName); if (dr.Length > 0) { Name = dr[0]["目的字段"].ToString(); ...

两个相似SQL的查询结果，以前未曾注意【图】

a.sysno=1;select a.*, case when x.resno is null then 0 else 1 end as isown from prm_res aleft join (select b.resno from prm_res binner join prmg_role_res c on b.resno=c.resnoinner join prmg_acct_role d on d.roleno=c.roleno and d.acct=1) as xon a.resno=x.resno and a.sysno=1;谁知道啥情况？欢迎留言本文出自 “熔岩” 博客，请务必保留此出处http://lavasoft.blog.51cto.com/62575/1941135两个相似SQL的查询结...

sql查询表中根据某列排序的任意行语句

代码如下: select * from (select t.*, row_number() over(order by 列 desc) r from 表 t) where r <= 某行 and r>=某行

有关springBoot-jpa详细介绍，包括数据库映射和命名查询法等【代码】

在这里就推荐原地址，可以访问这个链接有详细介绍。注意：如果是ssh框架做模糊查询的时候，最好是自己写HQL语句，要不然出不了数据，反正我试过了。 ssh框架的HQL例子：@Query("SELECT it FROM magneto.Xmgl it WHERE it.ztId=?1 and it.listType=?2 and it.name like %?3% and it.projectCode like %?4%") Page<Xmgl> findAllByZtIdAndListTypeAndNameLikeAndProjectCodeLike(int ztId, ListType listType, String name, Stri...

07_动态SQL与模糊查询【代码】

( id int primary key auto_increment, name varchar(10), age int(3)); insert into d_user(name,age) values(‘Tom‘,12); insert into d_user(name,age) values(‘Bob‘,13); insert into d_user(name,age) values(‘Jack‘,18);3 ConditionUser(查询条件实例类）private String name;private int minAge;private int maxAge;4 userMapper.xml(映射文件)<mapper namespace="cn.imentors.mybatis.test7.userMapper"> <!-- ...

K大数查询 HYSBZ - 3110【代码】

K大数查询 HYSBZ - 3110 本来是刷整体二分的，被这个sb题折腾了一下午，用cin就RE, 用scanf就过了＝_=收获就是偶然学到了树状数组区间修改区间查询的写法吧。。。 1 #include <iostream>2 #include <cstring>3 #include <cstdio>4usingnamespace std;5#define LL long long 6constint maxn = 1e5 + 10;7constint maxq = 5e4 + 10;8struct Qry{9int a, b;10 LL c;11int id;12 Qry(int a = 0, int b = 0, LL c = 0, int id =...

输入框中根据用户输入内容动态查询

前端 UI 设计里面有一个经常需要用到的实时搜索场景：当用户在 inpu 里面键入新的内容后，不依赖于用户触发(如点击按钮)，立即自动向后端发起 ajax 查询并展示结果。这一需求有多种实现方案，典型的是可以设置一个定时器轮询 input 中的内容是否发生变化，若变化了则立即发起后端查询。这种方案思路比较清晰，但有一个弊端：需要定时器时时运行，且设置的轮询时间间隔要求较高：若此值太小则会对用户的每个“中间输入”发起搜索，...

sql子查询【代码】

子查询就是在简单查询中嵌套查询(where子句里面嵌套) select name from tablename where id in (select id from tablename where num in (100,101) )可以一直嵌套下去但是由于性能的限制,实际上不能嵌套太多的子查询当然,不一定是in,其他也行或者在select子句里进行嵌套 select name,(select * count(distinct name) from tablename) as other from tablename order by name;在from子句里面嵌套 select * from (select id,name...

sql 查询 aeiou元素【图】

查询city中aeiou元素，并且不能重复select distinct city from station where regexp_like (lower(city),‘^a|^e|^i|^o|^u‘);sql 查询 aeiou元素标签：jpg hal src https challenge 不能 like exp ges 本文系统来源：http://www.cnblogs.com/Angella/p/6680337.html

数据库SQL SELECT查询的工作原理【图】

作为B/S架构的开发人员，总是离不开数据库。一般开发员只会应用SQL的四条经典语句:select，insert，delete，update。但是我从来没有研究过它们的工作原理，这篇我想说一说select在数据库中的工作原理。 B/S架构中最经典的话题无非于三层架构，可以大概分为数据层，业务逻辑层和表示层，而数据层的作用一般都是和数据库交互，例如查询记录。我们经常是写好查询SQL，然后调用程序执行SQL。但是它内部的工作流程是怎样的呢？先做哪一步...

[ZJJOI2013]K大数查询整体二分【代码】

[ZJJOI2013]K大数查询链接luogu思路整体二分。代码#include <bits/stdc++.h> #define ll long long using namespace std; const ll _=5e5+7; ll read() {ll x=0,f=1;char s=getchar();for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';return x*f; } ll n,m,ans[_]; struct OPT {ll opt,a,b,c,id;}Q[_],tmp1[_],tmp2[_]; namespace seg {#define ls rt<<1#define rs rt<<1|1struct ...

Flask-SQLAlchemy - 不使用外键连表查询。记得常回来看我【代码】【图】

相比于 Django 的 ORM ，SQLAlchemy "不依靠外键进行跨表联查" 的解决方案就比较多。没啥好说的，只能怪自己学艺不精.. _(:з」∠)_ 解决办法query = database.session().query(models.A, models.B) query = query.join(models.B, models.B.UUID == models.A.UUID).filter(models.a.UUID == ‘2018061520180621‘).filter(models.b.xx= ‘haha‘) # 第二个filter可以继续过滤、join 或者删掉.. data = query.all() >>> ...

SQL分组查询GroupBy加having【代码】

一.分组查询概述作用：“Group By”从字面意义上理解就是根据“By”指定的规则对数据进行分组，所谓的分组就是将一个“数据集”划分成若干个“小区域”，然后针对若干个“小区域”进行数据处理。1.使用group by进行分组查询在使用group by关键字时，在select列表中可以指定的项目是有限制的，select语句中仅许以下几项：〉被分组的列〉为每个分组返回一个值得表达式，例如用一个列名作为参数的聚合函数group by的使用在这只写几个例...

查询 - 相关标签

查询经纬度查询条件

首页 / 更多教程 / K大数查询 HYSBZ - 3110

K大数查询 HYSBZ - 3110

内容导读

内容图文

K大数查询

内容总结

内容备注

内容手机端

【K大数查询 HYSBZ - 3110】教程文章相关的互联网学习教程文章

sql sever 查询语句【代码】

.NET应用架构设计—面向查询的领域驱动设计实践（调整传统三层架构，外加维护型的业务开关）

DataTable查询数据集

两个相似SQL的查询结果，以前未曾注意【图】

sql查询表中根据某列排序的任意行语句

有关springBoot-jpa详细介绍，包括数据库映射和命名查询法等【代码】

07_动态SQL与模糊查询【代码】

K大数查询 HYSBZ - 3110【代码】

输入框中根据用户输入内容动态查询

sql子查询【代码】

sql 查询 aeiou元素【图】

数据库SQL SELECT查询的工作原理【图】

[ZJJOI2013]K大数查询整体二分【代码】

Flask-SQLAlchemy - 不使用外键连表查询。记得常回来看我【代码】【图】

SQL分组查询GroupBy加having【代码】

查询 - 相关标签

更多教程 - 最新教程

更多教程 - 最热教程