首页 > 代码库 > 省队集训 Day6 序列
省队集训 Day6 序列
【题目大意】
给出$n$个数的序列$a_1, a_2, ..., a_n$，有$m$次操作，为下面三种：
$A~l~r~d$：区间$[l,r]$，全部加$d$。
$M~l~r~d$：区间$[l,r]$，对$d$取max。
$Q~x$：询问$a_x$的值。
对于30%的数据，$n, m\leq 10^4$；
对于60%的数据，保证数据随机；
对于100%的数据，满足$n, m \leq 10^5$，所有数的绝对值不超过$2^{31} - 1$。保证也是随机的。
【题解】
显然正解是吉司机线段树，我不会，那怎么办？分块！！！
对于100%的数据的那个性质我是拿数据后才知道的。
考场写了$O(n * (n/B) * logB)$的常数大的跟*一样的分块做法，其中$B = 32$，理论上$B = 128$左右比较优，可能是我常数太大了只能开32。。。
由于数据随机（迷），就过了……
具体是这样的，每个操作如果涉及部分块，直接暴力重构。
每个块内排序后，发现操作2相当于找一段前缀，改成$d$，然后将这些数的次数全部+1，这个可以方便用线段树维护，找的话线段树上二分即可。
操作1的话相当于块全局加，然后这些块的次数全部+1（需要特判$d=0$），可以记录一个全局标记来做。
然后就很方便维护信息了（吧），为了线段树上二分可能需要记录一个最小值。
然后调调边界啊，开开longlong啊，卡了卡常就过了。。
# include <stdio.h> # include <assert.h> # include <string.h> # include <iostream> # include <algorithm> # define getchar getchar_unlocked using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; # ifdef WIN32 # define LLFORMAT "%I64d" # else # define LLFORMAT "%lld" # endif # define beg BEG # define end END const int N = 1e5 + 10, B = 3205, SN = 128 + 5; const ll inf = 1e17; inline int getint() { int x = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) { if(ch == ‘-‘) f = 0; ch = getchar(); } while(isdigit(ch)) x = (x<<3) + (x<<1) + ch - ‘0‘, ch = getchar(); return f ? x : -x; } int n, m, beg[B], end[B], len[B], bl[N], id[B][33]; struct pa { ll a; int t; pa() {} pa(ll a, int t) : a(a), t(t) {} inline friend bool operator < (pa a, pa b) { return a.a < b.a; } inline friend pa operator + (pa a, pa b) { return pa(min(a.a, b.a), 0); } }p[N]; pa g[B]; int gn = 0; ll add[B]; int addt[B]; struct SMT { // 区间覆盖，对于a做，区间加法，对于t做 pa w[SN]; int tag[SN]; ll cov[SN]; bool hc[SN]; # define ls (x<<1) # define rs (x<<1|1) inline void up(int x) { w[x] = w[ls] + w[rs]; } inline void pushtag(int x, int tg) { tag[x] += tg; w[x].t += tg; } inline void pushcov(int x, ll c) { w[x].a = c; cov[x] = c; hc[x] = 1; } inline void down(int x) { if(hc[x]) { pushcov(ls, cov[x]); pushcov(rs, cov[x]); hc[x] = 0; cov[x] = 0; } if(tag[x]) { pushtag(ls, tag[x]); pushtag(rs, tag[x]); tag[x] = 0; } } inline void build(int x, int l, int r) { tag[x] = cov[x] = 0; hc[x] = 0; if(l == r) { w[x] = g[l]; return ; } int mid = l+r>>1; build(ls, l, mid); build(rs, mid+1, r); up(x); } inline void cover(int x, int l, int r, int L, int R, ll p) { if(L <= l && r <= R) { pushcov(x, p); pushtag(x, 1); return ; } down(x); int mid = l+r>>1; if(L <= mid) cover(ls, l, mid, L, R, p); if(R > mid) cover(rs, mid+1, r, L, R, p); up(x); } inline void gans(int x, int l, int r) { if(l == r) { g[++gn] = w[x]; return ; } down(x); int mid = l+r>>1; gans(ls, l, mid); gans(rs, mid+1, r); } inline pa gs(int x, int l, int r, int ps) { // cerr << x << ‘ ‘ << w[x].a << ‘ ‘ << w[x].t << endl; if(l == r) return w[x]; down(x); int mid = l+r>>1; if(ps <= mid) return gs(ls, l, mid, ps); else return gs(rs, mid+1, r, ps); } // find the last number that < p inline int find(int x, int l, int r, ll p) { if(l == r) return l; down(x); int mid = l+r>>1; if(w[rs].a < p) return find(rs, mid+1, r, p); else return find(ls, l, mid, p); } inline void debug(int x, int l, int r) { printf("x = %d, min = " LLFORMAT "\n", x, w[x].a); if(l == r) { printf(" times = %d\n", w[x].t); return ; } int mid = l+r>>1; debug(ls, l, mid); debug(rs, mid+1, r); } # undef ls # undef rs }T[B]; int tid[B]; inline bool cmp(int x, int y) { return p[x] < p[y]; } namespace prepare { inline void deal(int x) { register int *pid = id[x], Len; Len = len[x] = end[x] - beg[x] + 1; for (register int i=1; i<=Len; ++i) tid[i] = beg[x] + i - 1; sort(tid+1, tid+Len+1, cmp); for (register int i=1; i<=Len; ++i) g[i] = p[tid[i]]; T[x].build(1, 1, Len); for (register int i=1; i<=Len; ++i) pid[i] = tid[i]; } } namespace option1 { inline void deal(int x, int l, int r, int c) { register int *pid = id[x], Len = len[x]; gn = 0, T[x].gans(1, 1, Len); for (register int i=1; i<=Len; ++i) p[pid[i]] = g[i], tid[i] = beg[x] + i - 1; for (register int i=beg[x]; i<=end[x]; ++i) p[i].a += add[x], p[i].t += addt[x]; add[x] = 0; addt[x] = 0; for (register int i=l; i<=r; ++i) p[i].a += c, p[i].t ++; sort(tid+1, tid+Len+1, cmp); for (register int i=1; i<=Len; ++i) g[i] = p[tid[i]]; T[x].build(1, 1, Len); for (register int i=1; i<=Len; ++i) pid[i] = tid[i]; } inline void deal(int x, int c) { add[x] += c; addt[x] ++; } inline void main(int l, int r, int c) { register int L = bl[l], R = bl[r]; if(L == R) deal(L, l, r, c); else { deal(L, l, end[L], c); deal(R, beg[R], r, c); for (register int i=L+1; i<R; ++i) deal(i, c); } } } namespace option2 { inline void deal(int x, int l, int r, int c) { register int *pid = id[x], Len = len[x]; gn = 0, T[x].gans(1, 1, Len); for (register int i=1; i<=Len; ++i) p[pid[i]] = g[i], tid[i] = beg[x] + i - 1; for (register int i=beg[x]; i<=end[x]; ++i) p[i].a += add[x], p[i].t += addt[x]; add[x] = 0; addt[x] = 0; for (register int i=l; i<=r; ++i) if(p[i].a < c) p[i].a = c, p[i].t ++; sort(tid+1, tid+Len+1, cmp); for (register int i=1; i<=Len; ++i) g[i] = p[tid[i]]; // for (int i=1; i<=len[x]; ++i) cerr << g[i].a << ‘ ‘ << g[i].t << " ====\n"; T[x].build(1, 1, Len); for (register int i=1; i<=Len; ++i) pid[i] = tid[i]; // for (int i=1; i<=len[x]; ++i) cerr << id[x][i] << ‘ ‘; cout << " id end\n"; } inline void deal(int x, int c) { ll p = c - add[x]; if(T[x].w[1].a >= p) return ; else { int tp = T[x].find(1, 1, len[x], p); T[x].cover(1, 1, len[x], 1, tp, p); } } inline void main(int l, int r, int c) { register int L = bl[l], R = bl[r]; if(L == R) deal(L, l, r, c); else { deal(L, l, end[L], c); deal(R, beg[R], r, c); for (register int i=L+1; i<R; ++i) deal(i, c); } } } namespace option3 { inline pa main(int x) { register int X = bl[x], *pid = id[X]; pa ret = pa(-inf, 0); for (register int i=1; i<=len[X]; ++i) if(pid[i] == x) { ret = T[X].gs(1, 1, len[X], i); break; } if(ret.a != -inf) ret.a += add[X]; ret.t += addt[X]; return ret; } } int main() { freopen("seq4.in", "r", stdin); freopen("seq.out", "w", stdout); const int BB = 32; n = getint(); for (register int i=1; i<=n; ++i) p[i] = pa(getint(), 0); for (register int i=1; i<=n; ++i) bl[i] = (i-1)/BB + 1; m = bl[n]; for (register int i=1; i<=m; ++i) beg[i] = (i-1)*BB+1, end[i] = i*BB; end[m] = n; for (register int i=1; i<=m; ++i) prepare :: deal(i); int Q = getint(); static int l, r, c; static char ch; pa t; while(Q--) { ch = getchar(); while(!isupper(ch)) ch = getchar(); // T[1].debug(1, 1, len[1]); // for (int i=1; i<=len[1]; ++i) cout << id[1][i] << ‘ ‘; cout << endl; if(ch == ‘A‘) { l = getint(), r = getint(), c = getint(); if(!c) continue; option1 :: main(l, r, c); } else if(ch == ‘M‘) { l = getint(), r = getint(), c = getint(); option2 :: main(l, r, c); } else { l = getint(); t = option3 :: main(l); printf(LLFORMAT " %d\n", t.a, t.t); } } return 0; }
省队集训 Day6 序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。