题目
题目大意似乎和题目描述差不多,略。。。
题解
简单(精妙)而慢的解法
对某个区间排序。
这种操作如果选一个数,将比它小的数当成0,比它大的数当成1。
那么,就变成了对区间覆盖0或1的问题。
所以我们可以来二分答案。
若将小于等于x的全赋成0, 大于x的全赋成1。
那么就是求最小的x,使询问的位置经过若干操作后等于0。
快叫好!!!
“吼啊!”
时间复杂度
二分
判定
总时间复杂度
代码
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 |
#include <cstdio> int n, m; int x[200000]; int tmp[200000]; int sum[1000000], tag[1000000]; int cas[200000], l[200000], r[200000]; int pos; void pushup(int k) { sum[k] = sum[k << 1] + sum[k << 1 | 1]; } void pushdown(int k, int l, int r) { if (tag[k] != -1) { int mid = l + r >> 1; tag[k << 1] = tag[k]; sum[k << 1] = tag[k] * (mid - l + 1); tag[k << 1 | 1] = tag[k]; sum[k << 1 | 1] = tag[k] * (r - mid); tag[k] = -1; } } void build(int k, int l, int r) { if (l == r) { sum[k] = tmp[l]; tag[k] = -1; return; } int mid = l + r >> 1; build(k << 1, l, mid); build(k << 1 | 1, mid + 1, r); pushup(k); tag[k] = -1; } void change(int k, int l, int r, int L, int R, int newvalue) { if (L <= l && r <= R) { tag[k] = newvalue; sum[k] = newvalue * (r - l + 1); return; } pushdown(k, l, r); int mid = l + r >> 1; if (L <= mid) { change(k << 1, l, mid, L, R, newvalue); } if (R > mid) { change(k << 1 | 1, mid + 1, r, L, R, newvalue); } pushup(k); } int query(int k, int l, int r, int L, int R) { if (L <= l && r <= R) { return sum[k]; } pushdown(k, l, r); int ans = 0; int mid = l + r >> 1; if (L <= mid) { ans += query(k << 1, l, mid, L, R); } if (R > mid) { ans += query(k << 1 | 1, mid + 1, r, L, R); } return ans; } bool check(int mid) { for (int i = 1; i <= n; i++) { tmp[i] = x[i] > mid; } build(1, 1, n); for (int i = 1; i <= m; i++) { if (cas[i] == 0) { int cnt1 = query(1, 1, n, l[i], r[i]); int cnt0 = r[i] - l[i] + 1 - cnt1; if (cnt0 > 0) { change(1, 1, n, l[i], l[i] + cnt0 - 1, 0); } if (cnt1 > 0) { change(1, 1, n, l[i] + cnt0, r[i], 1); } } else { int cnt1 = query(1, 1, n, l[i], r[i]); int cnt0 = r[i] - l[i] + 1 - cnt1; if (cnt1 > 0) { change(1, 1, n, l[i], l[i] + cnt1 - 1, 1); } if (cnt0 > 0) { change(1, 1, n, l[i] + cnt1, r[i], 0); } } } return query(1, 1, n, pos, pos) == 0; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &x[i]); } for (int i = 1; i <= m; i++) { scanf("%d%d%d", &cas[i], &l[i], &r[i]); } scanf("%d", &pos); int ll = 1; int rr = n; while (ll < rr) { int mid = ll + rr >> 1; if (check(mid)) { rr = mid; } else { ll = mid + 1; } } printf("%d\n", ll); return 0; } |
快而复杂(吐血)的解法
这种做法可以处理多个询问,还可以在线做。
那么是什么呢?
没错,模拟大法好!
。。。
开始第i个位置都表示区间$ [i,i] $,弄一棵动态开点的权值线段树,并且权值线段树里记录下i位置的值。
然后每棵线段树还有个rev表示是从大到小还是从小到大。
然后就可以模拟啦。
外面弄一棵线段树维护每个位置在哪个区间中。
然后修改操作就是找一段包含修改区间的连续的区间,头尾两个区间可能是部分包含的,所以还要用到线段树的split操作(雾),然后就是线段树的merge了。介绍线段树的合并与分裂的传送门。
这段代码居然让我码了一个多小时。。。
时间复杂度
每次操作最多split两次,所以main函数里最多split次,并且线段树节点数最多
个,所以最后的时间复杂度为
代码
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 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 |
#include <cstdio> #include <algorithm> int n, m; int root[200000], rev[200000]; int tag[1000000]; int num; int ch[10000000][2], sum[10000000]; void pushup(int k) { if (k) { sum[k] = sum[ch[k][0]] + sum[ch[k][1]]; } } void change(int &u, int l, int r, int pos, int delta) { num++; u = num; sum[u] = delta; if (l == r) { return; } int mid = l + r >> 1; if (pos <= mid) { change(ch[u][0], l, mid, pos, delta); } else { change(ch[u][1], mid + 1, r, pos, delta); } } int query(int k, int l, int r, int rank) { if (l == r) { return l; } int mid = l + r >> 1; if (rank <= sum[ch[k][0]]) { return query(ch[k][0], l, mid, rank); } else { return query(ch[k][1], mid + 1, r, rank - sum[ch[k][0]]); } } std::pair<int, int> split(int x, int rank) { if (! x) { return std::make_pair(0, 0); } if (rank <= sum[ch[x][0]]) { std::pair<int, int> tmp = split(ch[x][0], rank); num++; ch[num][0] = tmp.first; ch[x][0] = tmp.second; sum[num] = rank; sum[x] = sum[x] - rank; return std::make_pair(num, x); } else { std::pair<int, int> tmp = split(ch[x][1], rank - sum[ch[x][0]]); num++; ch[num][1] = tmp.second; ch[x][1] = tmp.first; sum[num] = sum[x] - rank; sum[x] = rank; return std::make_pair(x, num); } } std::pair<int, int> split(int x, int rank, int cas) { std::pair<int, int> ans; if (cas) { ans = split(x, sum[x] - rank); std::swap(ans.first, ans.second); return ans; } else { ans = split(x, rank); return ans; } } void merge(int &x, int y) { if (! y) { return; } if (! x) { x = y; return; } sum[x] += sum[y]; merge(ch[x][0], ch[y][0]); merge(ch[x][1], ch[y][1]); } void pushdownbelong(int k) { if (tag[k]) { tag[k << 1] = tag[k << 1 | 1] = tag[k]; tag[k] = 0; } } void buildbelong(int k, int l, int r) { tag[k] = 0; if (l == r) { tag[k] = l; return; } int mid = l + r >> 1; buildbelong(k << 1, l, mid); buildbelong(k << 1 | 1, mid + 1, r); } void changebelong(int k, int l, int r, int L, int R, int newvalue) { if (L <= l && r <= R) { tag[k] = newvalue; return; } pushdownbelong(k); int mid = l + r >> 1; if (L <= mid) { changebelong(k << 1, l, mid, L, R, newvalue); } if (R > mid) { changebelong(k << 1 | 1, mid + 1, r, L, R, newvalue); } } int querybelong(int k, int l, int r, int pos) { if (l == r) { return tag[k]; } pushdownbelong(k); int mid = l + r >> 1; if (pos <= mid) { return querybelong(k << 1, l, mid, pos); } else { return querybelong(k << 1 | 1, mid + 1, r, pos); } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); change(root[i], 1, n, x, 1); rev[i] = 0; } buildbelong(1, 1, n); for (int i = 1; i <= m; i++) { int cas, l, r; scanf("%d%d%d", &cas, &l, &r); int ll = querybelong(1, 1, n, l); int rr = querybelong(1, 1, n, r); if (ll == rr) { std::pair<int, int> x1, x2; int v = rev[ll]; x1 = split(root[ll], l - ll, v); x2 = split(x1.second, r - l + 1, v); if (sum[x1.first]) { root[ll] = x1.first; rev[ll] = v; changebelong(1, 1, n, ll, ll + sum[x1.first] - 1, ll); } if (sum[x2.first]) { root[l] = x2.first; rev[l] = cas; changebelong(1, 1, n, l, l + sum[x2.first] - 1, l); } if (sum[x2.second]) { root[r + 1] = x2.second; rev[r + 1] = v; changebelong(1, 1, n, r + 1, r + 1 + sum[x2.second] - 1, r + 1); } } else { int now = 0; for (int j = ll + sum[root[ll]]; j != rr; j = j + sum[root[j]]) { merge(now, root[j]); } int v; std::pair<int, int> tmp; v = rev[ll]; tmp = split(root[ll], l - ll, v); if (sum[tmp.first]) { root[ll] = tmp.first; rev[ll] = v; changebelong(1, 1, n, ll, ll + sum[tmp.first] - 1, ll); } merge(now, tmp.second); v = rev[rr]; tmp = split(root[rr], r - rr + 1, v); if (sum[tmp.second]) { root[r + 1] = tmp.second; rev[r + 1] = v; changebelong(1, 1, n, r + 1, r + 1 + sum[tmp.second] - 1, r + 1); } merge(now, tmp.first); root[l] = now; rev[l] = cas; changebelong(1, 1, n, l, r, l); } } int pos; scanf("%d", &pos); int kk = querybelong(1, 1, n, pos); if (rev[kk]) { printf("%d\n", query(root[kk], 1, n, sum[root[kk]] - (pos - kk + 1) + 1)); } else { printf("%d\n", query(root[kk], 1, n, pos - kk + 1)); } return 0; } |
太强了吧!