Luogu P3168 [CQOI2015]任务查询系统

时间:2022-04-15 05:26:24

题目链接 \(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]任务查询系统的更多相关文章

  1. 「Luogu P3168 &lbrack;CQOI2015&rsqb;任务查询系统」

    介绍本题的两种做法: 方法1 前置芝士 线段树:一个很重要的数据结构. 树状数组:一个很重要的数据结构. 具体实现 区间修改,单点查询很容易就会想到树状数组了,至于查询前k个数的和又可以丢给权值线段树 ...

  2. P3168 &lbrack;CQOI2015&rsqb;任务查询系统

    题目地址:P3168 [CQOI2015]任务查询系统 主席树的模板题 更模板的在这儿:P3834 [模板]可持久化线段树 1(主席树) 形象的说,P3834是"单点修改,区间查询&quot ...

  3. bzoj3932 &sol; P3168 &lbrack;CQOI2015&rsqb;任务查询系统(主席树&plus;差分)

    P3168 [CQOI2015]任务查询系统 看到第k小,就是主席树辣 对于每一段任务(a,b,k),在版本a的主席树+k,版本b+1的主席树-k 同一时间可能有多次修改,所以开个vector存操作, ...

  4. 洛谷 P3168 &lbrack;CQOI2015&rsqb;任务查询系统 解题报告

    P3168 [CQOI2015]任务查询系统 题目描述 最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分. 超级计算机中的任务用三元组\((S_i,E_i,P_i) ...

  5. 洛谷P3168 &lbrack;CQOI2015&rsqb;任务查询系统 &lbrack;主席树,差分&rsqb;

    题目传送门 任务查询系统 题目描述 最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分.超级计算机中的任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任 ...

  6. ●洛谷P3168 &lbrack;CQOI2015&rsqb;任务查询系统

    题链: https://www.luogu.org/problemnew/show/P3168题解: 主席树 强制在线? 那就直接对每一个前缀时间建一个线段树(可持久化线段树),线段树维护优先度权值. ...

  7. P3168 &lbrack;CQOI2015&rsqb;任务查询系统&lpar;主席树&rpar;

    题目描述 最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分.超级计算机中的任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si秒开始,在第Ei ...

  8. 洛谷P3168 &lbrack;CQOI2015&rsqb;任务查询系统

    #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #in ...

  9. p3168 &lbrack;CQOI2015&rsqb;任务查询系统(差分&plus;主席树)

    恕我才学浅薄,一开始想到的是树状数组+线段树,然后看了题解才第一次见到了差分这种神奇的科技 仔细想想,主席树的本质不就是前缀和嘛,加上一个差分也是可以的,没想到真是罪过罪过 对时间维护一个差分 在Si ...

随机推荐

  1. html学习心得

    注释:浏览器会自动地在段落的前后添加空行.(<p> 是块级元素) 提示:使用空的段落标记 <p></p> 去插入一个空行是个坏习惯.用 <br /> 标 ...

  2. 在单线程中你最好使用ArrayList而不是Vector

    <java核心技术卷一>571页上提到Vector类的所有方法都是同步的.可以由两个线程安全地访问同一个Vector对象.显然,如果可以确定我们不会在多个线程中对这个数组进行操作的话,我们 ...

  3. Ubuntu 14&period;04 安装 Xilinx ISE 14&period;7 全过程

    生命在于折腾. 这个帖子作为我安装xilinx ISE 14.7版本一个记录.希望给需要的人一些帮助,这些内容绝大部分也是来源于互联网. 软硬件: lsb_release -a No LSB modu ...

  4. 为了启动我在openshift的angular应用

    在Windows环境下搭建OpenShift环境,安装客户端工具rhc,首先需要安装Ruby和Git,参阅https://developers.openshift.com/en/getting-sta ...

  5. Angular service&comma; 服务

      早上开车上班, 发现车快没油了, 于是拐进加油站. 有一辆出租车也在加油..   Angular service在一个应用里是以单例形式存在的. 这个单例的实例是由service factory( ...

  6. 大学生程序猿IT情书&OpenCurlyDoubleQuote;2014爱的告白挑战赛”获奖名单及优秀情书展示系列之 - 【IT术语】情书&plus;【搞笑另类】情书

    经过专家评委们的层层精心评选和认真讨论,恭喜下面同学终于入选CSDN高校俱乐部"大学生程序猿IT情书2014爱的告白挑战赛活动"优胜者名单.获奖者将在本周内收到邮件通知.请依照邮件 ...

  7. android入门——UI&lpar;4&rpar;

    GridView控件实现菜单 <?xml version="1.0" encoding="utf-8"?> <LinearLayout xml ...

  8. QQ互联 redirect uri is illegal&lpar;100010&rpar;的解决办法,很简单

    我的地址栏内容是:http://openapi.qzone.qq.com/oauth/show?which=ConfirmPage&display=pc&response_type=c ...

  9. react-native 打开设置界面

    iOS iOS打开设置还是比较简单的,使用Linking组件即可: Linking.openURL('app-settings:') .catch(err => console.log('err ...

  10. C&num; 把ABCD转换成数字

    每倒题得选项可能是多选或者单选. public static string LetterTransformationNum(string answer, int type) { string num ...