[CQOI2015]任务查询系统

把一个任务拆成两个,在s时加入,在e+1时减去即可
直接离散化后上主席树

# include <bits/stdc++.h>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(5e6 + 10); IL ll Read(){
RG char c = getchar(); RG ll x = 0, z = 1;
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
} int ls[_], rs[_], rt[_], sz[_], n, m, p[_], id[_], s[_], e[_];
int num, len, type[_], tim[_], val[_], cnt, ID[_];
ll sum[_]; IL bool Cmp(RG int x, RG int y){ return tim[x] < tim[y]; } IL void Build(RG int &x, RG int l, RG int r){
x = ++num;
if(l == r) return;
RG int mid = (l + r) >> 1;
Build(ls[x], l, mid); Build(rs[x], mid + 1, r);
} IL void Modify(RG int &x, RG int l, RG int r, RG int tp, RG int va){
rt[++num] = rt[x]; ls[num] = ls[x]; rs[num] = rs[x];
sz[num] = sz[x] + tp; sum[num] = sum[x] + tp * p[va];
x = num;
if(l == r) return;
RG int mid = (l + r) >> 1;
if(va <= mid) Modify(ls[x], l, mid, tp, va);
else Modify(rs[x], mid + 1, r, tp, va);
} IL ll Query(RG int x, RG int l, RG int r, RG int k){
if(l == r) return 1LL * p[l] * k;
RG int mid = (l + r) >> 1;
if(k <= sz[ls[x]]) return Query(ls[x], l, mid, k);
return sum[ls[x]] + Query(rs[x], mid + 1, r, k - sz[ls[x]]);
} int main(RG int argc, RG char* argv[]){
m = Read(); n = Read();
for(RG int i = 1; i <= m; ++i) s[i] = Read(), e[i] = Read(), id[i] = p[i] = Read();
sort(p + 1, p + m + 1); len = unique(p + 1, p + m + 1) - p - 1;
for(RG int i = 1; i <= m; ++i){
id[i] = lower_bound(p + 1, p + len + 1, id[i]) - p;
++cnt; ID[cnt] = cnt; type[cnt] = 1; tim[cnt] = s[i]; val[cnt] = id[i];
++cnt; ID[cnt] = cnt; type[cnt] = -1; tim[cnt] = e[i] + 1; val[cnt] = id[i];
}
sort(ID + 1, ID + cnt + 1, Cmp);
Build(rt[0], 1, len);
for(RG int t = 1, j = 1; t <= n; t++){
rt[t] = rt[t - 1];
for(; t == tim[ID[j]]; ++j){
RG int i = ID[j];
Modify(rt[tim[i]], 1, len, type[i], val[i]);
}
}
for(RG ll i = 1, ans = 1; i <= n; ++i){
RG ll x = Read(), a = Read(), b = Read(), c = Read(), k = 1 + (a * ans + b) % c;
k = min(k, (ll)sz[rt[x]]);
ans = Query(rt[x], 1, len, k);
printf("%lld\n", ans);
}
return 0;
}
上一篇:PHPCMS V9 模块开发 二次开发实例 留言本


下一篇:C读txt到二维数组