题目链接 \(Click\) \(Here\)
差分主席树,就是把主席树做成一个差分前缀和的形式,还是很容易想到的。
写主席树的时候几个注意点:
- 查询可能开始于所有任务之前,二分任务点要把左边界设置为\(0\)
- 记得开\(longlong\)
- 主席树通用细节:查询结束后的边界可能有残余答案未统计。即一个权值里的数,选了太多,不选太少,二分后要手动选上漏掉的部分。
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
const int INF = 1e7;
#define int long long
int m, n, pre = 1;
struct Task {
int t, w, p;
bool operator < (Task rhs) const {
return t < rhs.t;
}
}task[N << 1];
int tot = 1, rt[N << 1];
#define mid ((l + r) >> 1)
struct Segment_Node {
int sz, ls, rs, sum;
}t[N << 6];
int modify (int _rt, int l, int r, int w, int del) {
int p = ++tot;
t[p].sz = t[_rt].sz + del;
t[p].sum = t[_rt].sum + del * w;
if (l != r) {
if (w <= mid) {
t[p].ls = modify (t[_rt].ls, l, mid, w, del), t[p].rs = t[_rt].rs;
} else {
t[p].rs = modify (t[_rt].rs, mid + 1, r, w, del), t[p].ls = t[_rt].ls;
}
} else {
t[p].ls = t[p].rs = 0;
}
return p;
}
int query (int rt, int l, int r, int k) {
int sum = 0; k = min (k, t[rt].sz);
while (l < r) {
int lch = t[t[rt].ls].sz;
int lsum = t[t[rt].ls].sum;
if (k >= lch) {
k -= lch;
sum += lsum;
l = mid + 1;
rt = t[rt].rs;
} else {
r = mid;
rt = t[rt].ls;
}
}
return sum + k * r;
}
#undef mid
signed main () {
// freopen ("data.in", "r", stdin);
// freopen ("data.out", "w", stdout);
t[0] = (Segment_Node) {0, 0, 0, 0};
cin >> m >> n;
for (int i = 1; i <= m; ++i) {
static int S, E, P;
cin >> S >> E >> P;
task[i * 2 - 1] = (Task) {S, +1, P};
task[i * 2] = (Task) {E + 1, -1, P};
}
sort (task + 1, task + 1 + m * 2);
for (int i = 1; i <= m * 2; ++i) {
rt[i] = modify (rt[i - 1], 1, 1e7, task[i].p, task[i].w);
// printf ("task[%d] = {%d, %d, %d}\n", i, task[i].t, task[i].w, task[i].p);
}
for (int i = 1; i <= n; ++i) {
static int X, K, A, B, C;
cin >> X >> A >> B >> C;
K = 1 + (A * pre + B) % C;
int l = 0, r = m * 2;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (task[mid].t <= X) {
l = mid;
} else {
r = mid - 1;
}
}
// printf ("l = %d, k = %d\n", l, K);
cout << (pre = query (rt[l], 1, 1e7, K)) << endl;
}
}
Luogu P3168 [CQOI2015]任务查询系统的更多相关文章
-
「Luogu P3168 [CQOI2015]任务查询系统」
介绍本题的两种做法: 方法1 前置芝士 线段树:一个很重要的数据结构. 树状数组:一个很重要的数据结构. 具体实现 区间修改,单点查询很容易就会想到树状数组了,至于查询前k个数的和又可以丢给权值线段树 ...
-
P3168 [CQOI2015]任务查询系统
题目地址:P3168 [CQOI2015]任务查询系统 主席树的模板题 更模板的在这儿:P3834 [模板]可持久化线段树 1(主席树) 形象的说,P3834是"单点修改,区间查询" ...
-
bzoj3932 / P3168 [CQOI2015]任务查询系统(主席树+差分)
P3168 [CQOI2015]任务查询系统 看到第k小,就是主席树辣 对于每一段任务(a,b,k),在版本a的主席树+k,版本b+1的主席树-k 同一时间可能有多次修改,所以开个vector存操作, ...
-
洛谷 P3168 [CQOI2015]任务查询系统 解题报告
P3168 [CQOI2015]任务查询系统 题目描述 最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分. 超级计算机中的任务用三元组\((S_i,E_i,P_i) ...
-
洛谷P3168 [CQOI2015]任务查询系统 [主席树,差分]
题目传送门 任务查询系统 题目描述 最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分.超级计算机中的任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任 ...
-
●洛谷P3168 [CQOI2015]任务查询系统
题链: https://www.luogu.org/problemnew/show/P3168题解: 主席树 强制在线? 那就直接对每一个前缀时间建一个线段树(可持久化线段树),线段树维护优先度权值. ...
-
P3168 [CQOI2015]任务查询系统(主席树)
题目描述 最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分.超级计算机中的任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si秒开始,在第Ei ...
-
洛谷P3168 [CQOI2015]任务查询系统
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #in ...
-
p3168 [CQOI2015]任务查询系统(差分+主席树)
恕我才学浅薄,一开始想到的是树状数组+线段树,然后看了题解才第一次见到了差分这种神奇的科技 仔细想想,主席树的本质不就是前缀和嘛,加上一个差分也是可以的,没想到真是罪过罪过 对时间维护一个差分 在Si ...
随机推荐
-
html学习心得
注释:浏览器会自动地在段落的前后添加空行.(<p> 是块级元素) 提示:使用空的段落标记 <p></p> 去插入一个空行是个坏习惯.用 <br /> 标 ...
-
在单线程中你最好使用ArrayList而不是Vector
<java核心技术卷一>571页上提到Vector类的所有方法都是同步的.可以由两个线程安全地访问同一个Vector对象.显然,如果可以确定我们不会在多个线程中对这个数组进行操作的话,我们 ...
-
Ubuntu 14.04 安装 Xilinx ISE 14.7 全过程
生命在于折腾. 这个帖子作为我安装xilinx ISE 14.7版本一个记录.希望给需要的人一些帮助,这些内容绝大部分也是来源于互联网. 软硬件: lsb_release -a No LSB modu ...
-
为了启动我在openshift的angular应用
在Windows环境下搭建OpenShift环境,安装客户端工具rhc,首先需要安装Ruby和Git,参阅https://developers.openshift.com/en/getting-sta ...
-
Angular service, 服务
早上开车上班, 发现车快没油了, 于是拐进加油站. 有一辆出租车也在加油.. Angular service在一个应用里是以单例形式存在的. 这个单例的实例是由service factory( ...
-
大学生程序猿IT情书“2014爱的告白挑战赛”获奖名单及优秀情书展示系列之 - 【IT术语】情书+【搞笑另类】情书
经过专家评委们的层层精心评选和认真讨论,恭喜下面同学终于入选CSDN高校俱乐部"大学生程序猿IT情书2014爱的告白挑战赛活动"优胜者名单.获奖者将在本周内收到邮件通知.请依照邮件 ...
-
android入门——UI(4)
GridView控件实现菜单 <?xml version="1.0" encoding="utf-8"?> <LinearLayout xml ...
-
QQ互联 redirect uri is illegal(100010)的解决办法,很简单
我的地址栏内容是:http://openapi.qzone.qq.com/oauth/show?which=ConfirmPage&display=pc&response_type=c ...
-
react-native 打开设置界面
iOS iOS打开设置还是比较简单的,使用Linking组件即可: Linking.openURL('app-settings:') .catch(err => console.log('err ...
-
C# 把ABCD转换成数字
每倒题得选项可能是多选或者单选. public static string LetterTransformationNum(string answer, int type) { string num ...