区间修改单点查询,又观察到是一个k小,考虑主席树上做差分
一开始样例疯狂挂,后来发现主席树在一个历史版本上只能修改一次,所以要开2*n个根结点,记录一下每个时间对应的根结点编号
然后80分,考虑到当一个排名的结点有w个而查询的k<w时会使答案变大,所以特判(但是一开始又喜闻乐见地把符号写反了)~
一通乱改+疯狂提交后水过
Code:
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const ll inf = (ll)1 << 60;
int n, qn, bel[N], maxn = 0;
ll val[N];
vector <int> ins[N], del[N];
struct Task {
int st, ed;
ll pri;
} a[N];
struct Innum {
int id;
ll val;
} in[N];
bool cmp(const Innum &x, const Innum &y) {
if(x.val != y.val) return x.val < y.val;
else return x.id < y.id;
}
template <typename T>
inline void read(T &X) {
X = 0;
char ch = 0;
T op = 1;
for(; ch > '9'|| ch < '0'; ch = getchar())
if(ch == '-') op = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar())
X = (X << 3) + (X << 1) + ch - 48;
X *= op;
}
inline int max(int x, int y) {
return x > y ? x : y;
}
inline void discrete() {
in[0].val = -inf;
sort(in + 1, in + 1 + n, cmp);
int cnt = 0;
for(int i = 1; i <= n; i++) {
if(in[i].val != in[i - 1].val) ++cnt;
maxn = max(maxn, cnt);
val[cnt] = in[i].val;
a[in[i].id].pri = cnt;
}
}
struct Node {
int lc, rc, cntSum;
ll priSum;
};
namespace PSegT {
int root[N << 1], nodeCnt;
Node s[N * 40];
#define mid (l + r) / 2
inline void up(int p) {
s[p].cntSum = s[s[p].lc].cntSum + s[s[p].rc].cntSum;
s[p].priSum = s[s[p].lc].priSum + s[s[p].rc].priSum;
}
void insert(int &p, int l, int r, int x, int pre, int type) {
p = ++nodeCnt;
s[p] = s[pre];
s[p].cntSum += type;
s[p].priSum += (ll)type * val[x];
if(l == r) return;
if(x <= mid) insert(s[p].lc, l, mid, x, s[pre].lc, type);
else insert(s[p].rc, mid + 1, r, x, s[pre].rc, type);
// up(p);
}
ll query(int p, int l, int r, int k) {
// if(l == r) return s[p].priSum;
if(l == r) return k < s[p].cntSum ? (ll)k * val[l] : s[p].priSum;
int now = s[s[p].lc].cntSum; ll res = 0;
if(k <= now) res = query(s[p].lc, l, mid, k);
else res = s[s[p].lc].priSum + query(s[p].rc, mid + 1, r, k - now);
return res;
}
void print(int p, int l, int r) {
printf("(%d %d %d %d %lld) ", p, s[p].lc, s[p].rc, s[p].cntSum, s[p].priSum);
if(l == r) return;
print(s[p].lc, l, mid);
print(s[p].rc, mid + 1, r);
}
#undef mid
} using namespace PSegT;
int main() {
read(n), read(qn);
for(int i = 1; i <= n; i++) {
read(a[i].st), read(a[i].ed), read(a[i].pri);
in[i].val = a[i].pri, in[i].id = i;
ins[a[i].st].push_back(i);
del[a[i].ed + 1].push_back(i);
}
discrete();
nodeCnt = root[0] = 0;
int rtCnt = 0;
for(int i = 1; i <= qn; i++) {
for(unsigned int j = 0; j < ins[i].size(); j++)
++rtCnt, insert(root[rtCnt], 1, maxn, a[ins[i][j]].pri, root[rtCnt - 1], 1);
for(unsigned int j = 0; j < del[i].size(); j++)
++rtCnt, insert(root[rtCnt], 1, maxn, a[del[i][j]].pri, root[rtCnt - 1], -1);
bel[i] = rtCnt;
}
/* for(int i = 1; i <= rtCnt; i++, printf("\n"))
print(root[i], 1, maxn); */
ll ans = 1;
for(int x, k, _a, _b, _c; qn--; ) {
read(x), read(_a), read(_b), read(_c);
k = 1 + ((ll)_a * ans + _b) % _c;
if(k >= s[root[bel[x]]].cntSum) printf("%lld\n", ans = s[root[bel[x]]].priSum);
else printf("%lld\n", ans = query(root[bel[x]], 1, maxn, k));
}
return 0;
}
感觉vector还挺快的……
转载于:https://www.cnblogs.com/CzxingcHen/p/9466449.html