bzoj 3065 带插入区间K小值
替罪羊套线段树 O(nlog^2n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 | #include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<ctime>#include<cmath>using namespace std;typedef pair<int, int> Pii;typedef long long LL;typedef long double db;#define rep(_,A,B) for(_=A;_<=B;++_)#define repi(_,A,B) for(register int _=A;_<=B;++_)#define FOR(_,A) for(int _=h[A];_;_=next[_])#define A first#define B second#define mp make_pairchar o;template<class O> void read(O&x){while(o=getchar(),o<'0'||o>'9');for(x=o^48;o=getchar(),o>='0'&&o<='9';)x=x*10+(o^48);}const int L = 70005, M = 10000005;const double alpha = 0.8;int n, Q;int a[L], id[L]; struct T { int l, r, s; T(){ l = r = s = 0; }}e[M];#define mid (l + r >> 1)int rec[M], rec_num, tot;inline int newnode(void) { if(rec_num) { e[rec[rec_num]] = T(); return rec[rec_num--]; } else return ++tot;}void reclaim(int &x) { if(!x) return ; rec[++rec_num] = x; reclaim(e[x].l), reclaim(e[x].r);}void ins(int &x, int l, int r, int y, int f) { if(!x)x = newnode(); e[x].s += f; //cout << "ins : " << x << " " << l << " " << r << " " << y << endl; if(l == r) return ; if(y <= mid) ins(e[x].l, l, mid, y, f); else ins(e[x].r, mid + 1, r, y, f); if(!e[x].s) reclaim(x), x = 0;}int root[L], lc[L], rc[L], Root;void build(int &x, int l, int r) { //cout << "build " << l << " " << r << endl; if(l > r) return ; x = id[mid]; build(lc[x], l, mid - 1), build(rc[x], mid + 1, r); repi(i, l, r) ins(root[x], 0, 70000, a[id[i]], 1);//, cout << "INS " << x << " " << i << endl;}void init(void) { cin >> n; repi(i, 1, n) read(a[i]), id[i] = i; build(Root, 1, n);}int q[L], cnt;void del(int &x) { //cout << "del " << x << endl; if(!x) return ; reclaim(root[x]), root[x] = 0; del(lc[x]); q[++cnt] = x; del(rc[x]); x = 0;}void rebuild(int &x) { //cout << "rebuild : " << x << endl; cnt = 0; del(x); repi(i, 1, cnt) id[i] = q[i];//, cout << id[i] << " "; cout << endl; build(x, 1, cnt);}int tmp;void ins(int &x, int y, int z) { //cout << "ins : " << x << " " << y << " " << z << endl; if(!x) { x = ++n, ins(root[x], 0, 70000, z, 1), a[x] = z; return ;} ins(root[x], 0, 70000, z, 1); int t = e[root[lc[x]]].s; if(y <= t) ins(lc[x], y, z); else ins(rc[x], y - t - 1, z); if(e[root[x]].s * alpha > max(e[root[lc[x]]].s, e[root[rc[x]]].s)) { if(tmp) { //cout << "rc2 " << rc[2] << endl; if(lc[x] == tmp) rebuild(lc[x]); else rebuild(rc[x]); } tmp = 0; } else tmp = x;} int modify(int x, int y, int val) { ins(root[x], 0, 70000, val, 1); //cout << "modify : " << x << " " << y << " " << val << endl; int z, t = e[root[lc[x]]].s; if(y <= t) z = modify(lc[x], y, val); else if(y - 1 == t)z = a[x], a[x] = val; else z = modify(rc[x], y - t - 1, val); ins(root[x], 0, 70000, z, -1); return z;}int q1[L], q2[L], cnt1, cnt2;void query(int x, int l, int r) { //cout << "query " << x << " " << l << " " << r << " "; int l_s = e[root[lc[x]]].s, r_s = e[root[x]].s; //cout << l_s << " " << r_s << endl; if(l == 1 && r == r_s) { q1[++cnt1] = root[x]; /*cout << "q1 " << x << endl;*/ return ; } if(l <= l_s + 1 && l_s + 1 <= r) q2[++cnt2] = a[x];//, cout << "q2 " << x << endl; if(r <= l_s) query(lc[x], l, r); else if(l > l_s + 1) query(rc[x], l - l_s - 1, r - l_s - 1); else { if(l <= l_s) query(lc[x], l, l_s); if(r > l_s + 1) query(rc[x], 1, r - l_s - 1); }}int Query(int x, int y, int k) { cnt1 = cnt2 = 0; query(Root, x, y); int l = 0, r = 70000; while(l < r) { int t = 0; repi(i, 1, cnt1) t += e[e[q1[i]].l].s; repi(i, 1, cnt2) if(l <= q2[i] && q2[i] <= mid) ++t; if(k <= t) { repi(i, 1, cnt1) q1[i] = e[q1[i]].l; r = mid; } else { repi(i, 1, cnt1) q1[i] = e[q1[i]].r; l = mid + 1, k -= t; } } return l;}void work(void) { cin >> Q; char op[5]; int x, y, k, ans = 0; while(Q--) { //cout << "Q rc2 " << Q + 1 << " " << rc[2] << endl; scanf("%s", op); read(x), read(y); x ^= ans, y ^= ans; if(op[0] == 'Q') read(k), printf("%d\n", ans = Query(x, y, k ^ ans)); else if(op[0] == 'M') modify(Root, x, y); else tmp = 0, ins(Root, x - 1, y); }}int main(void) { freopen("3065.in","r",stdin), freopen("3065.out","w",stdout); init(), work(); return 0;} |
bzoj 4025: 二分图
对时间分治，用启发式并查集维护一下，时间复杂度O(mlog^2n)，然而并查集常数极小，所以跑的比lct的O(mlogn)还快。
lct见http://wuzuofan.is-programmer.com/posts/89928.html 或者 http://c-sunshine.logdown.com
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | #include<cstdio>#include<algorithm>#include<iostream>#include<cstring>#include<ctime>#include<cmath>using namespace std;typedef pair<int, int> Pii;typedef long long LL;typedef long double db;#define rep(_,A,B) for(_=A;_<=B;++_)#define repi(_,A,B) for(register int _=A;_<=B;++_)#define FOR(_,A) for(int _=h[A];_;_=next[_])#define A first#define B second#define mp make_pairchar o;template<class O> void read(O&x){while(o=getchar(),o<'0'||o>'9');for(x=o^48;o=getchar(),o>='0'&&o<='9';)x=x*10+(o^48);}const int L = 100005, M = 200005;int n, m, T;struct M{ int u, v, st, ed; } e[M];int fa[L], d[L], a[L], q[M], top; Pii findx(int x) { int t = 0; for(; fa[x] != x; x = fa[x]) t ^= a[x]; return mp(x, t);}void merge(int x, int y, int dep) { if(d[x] > d[y]) swap(x, y); if(d[x] == d[y]) ++d[y], q[++top] = -y; fa[x] = y, a[x] = dep, q[++top] = x;}void resume(int t) { for(; top != t; --top) if(q[top] > 0) fa[q[top]] = q[top], a[q[top]] = 0; else --d[-q[top]];}void init(void) { cin >> n >> m >> T; repi(i, 1, m) { read(e[i].u), read(e[i].v), read(e[i].st), read(e[i].ed), ++e[i].st; if(e[i].st > e[i].ed) --m, --i; } repi(i, 1, n) fa[i] = i, d[i] = 1;}void solve(int l, int r, int r0) { int now = top, mid = l + r >> 1, i, j; rep(i, 1, r0) if(e[i].st <= l && r <= e[i].ed) { Pii x = findx(e[i].u), y = findx(e[i].v); int fx = x.A, fy = y.A, dep = !(x.B ^ y.B); if(fx != fy) merge(fx, fy, dep); else if(dep){ while(l <= r) puts("No"), ++l; resume(now); return ; } swap(e[r0--], e[i--]); } if(l == r) { puts("Yes"); return ; } for(i = 1, j = r0; i <= j; ++i) if(e[i].st > mid) swap(e[i--], e[j--]); solve(l, mid, j); for(i = 1, j = r0; i <= j; ++i) if(e[i].ed <= mid) swap(e[i--], e[j--]); solve(mid + 1, r, j); resume(now);}void work(void) { solve(1, T, m); }int main(void) { freopen("4025.in","r",stdin), freopen("4025.out","w",stdout); init(), work(); return 0;} |
