link

題目大意：維護一個序列

支持：

1.單點插入
2.單點刪除
3.區間翻轉
4.區間旋轉
5.區間加
6.區間賦值
7.詢問區間和
8.詢問區間極差
9.詢問區間與給定某個數差值絕對值的最小值
10.詢問區間第k小
11.詢問區間某個數排名

艸 11個操作 太毒瘤了 寫了一下午+晚上一節課（包含中途透徹時間

這么多操作各種平衡樹都上不了了，就塊狀鏈表

操作1:找到位置，把一個塊拆分，轉化為在快末尾插入
操作2:拆分塊，轉化為在塊末尾刪除
操作3:把翻轉的區間拎出來，每個區間打個翻轉標記，然后指針瞎指下
操作4:把旋轉的區間拎出來，每個區間打個旋轉標記
操作5:把區間拎出來打加法標記
操作6:把區間拎出來打賦值標記
操作7:把區間拎出來維護區間sum直接求和
操作8:每個塊維護s數組代表塊內元素排序好的結果，把區間拎出來后直接詢問，每個塊返回s[0]和s[size-1]
操作9:每個塊s數組里lower_bound和upper_bound
操作10:二分，轉化為操作11
操作11:每個塊s數組里lower_bound

細節：
0.每次操作后遍歷整個鏈表，檢查兩個相鄰塊大小太小就要合并

每個塊維護a[],s[],sz,sum,三個標記,鏈表指針

區間賦值標記優先級比另外兩個高，另外兩個可以共存

需要對某個塊進行大修改（分裂/合并）等之前要先清除標記，區間查詢內不能清除標記

塊尾insert和delete維護s數組要用插入排序及其逆操作

。。。忘了還有啥要注意的了

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;struct fuck
{int a[1000], s[1000]; //原序列/有序序列int sz, chenge_flag, add_flag;//chenge_flag存在時忽視add_flag和rev_flag//不存在時另外兩個標記互相不影響long long sum; //和bool rev_flag; //翻轉標記fuck *nex; //下個指針fuck(){sz = 0;sum = 0;nex = 0;chenge_flag = -1;add_flag = 0;rev_flag = false;}void access(){if (chenge_flag != -1){for (int i = 0; i < sz; i++) a[i] = s[i] = chenge_flag;sum = sz * (long long)chenge_flag;chenge_flag = -1;}else{if (add_flag != 0){for (int i = 0; i < sz; i++) a[i] += add_flag, s[i] += add_flag;sum += sz * (long long)add_flag;add_flag = 0;}if (rev_flag != 0) {reverse(a, a + sz); rev_flag ^= 1; }}}void gc(int x){add_flag = rev_flag = 0;chenge_flag = x;}void ga(int x){if (chenge_flag == -1) add_flag += x;else chenge_flag += x;}void gr(){if (chenge_flag == -1) rev_flag ^= 1;}void push_back(int x){access();//維護sif (sz == 0 || x >= s[sz - 1]) s[sz] = x;else for (int i = sz - 1; i >= 0; i--){s[i + 1] = s[i];if (i == 0 || s[i - 1] <= x) { s[i] = x; break; }}//維護sum和asum += (a[sz++] = x);}void delete_back(){access();sum -= a[sz - 1];for (int i = 0 ;i < sz; i++){if (s[i] == a[sz - 1]){for (int j = i + 1; j < sz; j++)s[j - 1] = s[j];}}sz--;}int qmax(){if (sz == 0) return 0;else if (chenge_flag != -1) return chenge_flag;else return s[sz - 1] + add_flag;}int qmin(){if (sz == 0) return 0x7fffffff;else if (chenge_flag != -1) return chenge_flag;else return s[0] + add_flag;}long long qsum(){if (chenge_flag != -1) return chenge_flag * (long long)sz;else return sum + add_flag * (long long)sz;}int query(int val){if (chenge_flag != -1) return chenge_flag < val ? sz : 0;val -= add_flag;return lower_bound(s, s + sz, val) - s;}int mindis(int val){if (sz == 0) return 0x7fffffff;if (chenge_flag != -1) return abs(chenge_flag - val);val -= add_flag;int pos0 = lower_bound(s, s + sz, val) - s;if (pos0 < sz && s[pos0] == val) return 0; else pos0--;int pos1 = upper_bound(s, s + sz, val) - s;if (pos0 >= 0 && pos0 < sz) pos0 = val - s[pos0];else pos0 = 0x7fffffff;if (pos1 >= 0 && pos1 < sz) pos1 = s[pos1] - val;else pos1 = 0x7fffffff;// printf("id = %p, [%d, %dreturn min(pos0, pos1);}void print(bool p = 0)const{printf("------------\n某一塊%p\n大小%d，和為%lld\nnex=%p\n", this, sz, sum, nex);printf("c=%d, a=%d, r=%d\n", chenge_flag, add_flag, rev_flag);for (int i = 0; i < sz; i++) { printf("%d ", a[i]);} printf("\n");for (int i = 0; i < sz; i++) { printf("%d ", s[i]);} printf("\n");if (p && nex != 0) nex->print(p); //輸出下一頁}
};int n, m, init[100010];
int blocksz, cur;
fuck *start;fuck *newnode() { return new fuck; }
void delnode(fuck *x) { delete x; }fuck *split(fuck *x, int pos) //x保留pos個元素，在x后面新建一個節點
{x->access();if (pos > x->sz) { printf("fuck!\n"); return 0; }fuck *res = newnode();//-----維護resfor (int i = pos; i < x->sz; i++)res->sum += (res->a[i - pos] = res->s[i - pos] = x->a[i]);res->sz = x->sz - pos;sort(res->s, res->s + res->sz);res->nex = x->nex;//-----維護xx->sz = pos; x->sum = 0;for (int i = 0; i < pos; i++) x->sum += (x->s[i] = x->a[i]);sort(x->s, x->s + pos);x->nex = res;return res;
}void merge(fuck *x)
{x->access();x->nex->access();fuck *p = x->nex;for (int i = 0; i < p->sz; i++)x->sum += (x->a[x->sz + i] = p->a[i]);x->sz += p->sz;x->nex = p->nex;for (int i = 0; i < x->sz; i++) x->s[i] = x->a[i];sort(x->s, x->s + x->sz);delnode(p);
}void maintain()
{for (fuck *p = start; p != 0; p = p->nex){while (p->nex != 0 && p->sz + p->nex->sz <= blocksz)merge(p);}
}void get(int l, int r, fuck* &lp, fuck* &rp)
{lp = start;while (lp != 0){if (l <= lp->sz) break;l -= lp->sz;lp = lp->nex;}if (l != 1)split(lp, l - 1), lp = lp->nex;rp = start;while (rp != 0){if (r <= rp->sz) break;r -= rp->sz;rp = rp->nex;}if (r != rp->sz)split(rp, r);
}void del(fuck *z)
{if (z->nex) del(z->nex);delete z;
}void chkmax(int &a, int b) { if (a < b) a = b; }
void chkmin(int &a, int b) { if (a > b) a = b; }int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++) scanf("%d", &init[i]);scanf("%d", &m);blocksz = sqrt(n + m / 5) * 3 / 4;fuck *now = start = newnode();for (int i = 1; i <= n; i++){now->push_back(init[i]);if (i % blocksz == 0 && i != n){fuck *p = newnode();now->nex = p;now = p;}}for (int opd, x, y, k, val, i = 1; i <= m; i++){scanf("%d", &opd);switch (opd){case 1:{scanf("%d%d", &x, &val);fuck *p = start;while (p != 0){if (x <= p->sz) break;x -= p->sz;p = p->nex;}//從0開始計數，放在p的第x個位置，也就是說p前面有x個數split(p, x);p->push_back(val);maintain();break;}case 2:{scanf("%d", &x);fuck *p = start;while (p != 0){if (x <= p->sz) break;x -= p->sz;p = p->nex;}//刪除第x個數，所以前面需要x個數split(p, x);p->delete_back();maintain();break;}case 3:{scanf("%d%d", &x, &y);fuck *l, *r;get(x, y, l, r), r = r->nex;vector<fuck*> li;split(l, 0);for (fuck *p = l->nex; p != r; p = p->nex)li.push_back(p), p->gr();l->nex = li[li.size() - 1];for (int i = li.size() - 1; i > 0; i--)li[i]->nex = li[i - 1];li[0]->nex = r;maintain();break;}case 4:{scanf("%d%d%d", &x, &y, &k);fuck *l1, *r1, *l2, *r2;get(x, y - k, l1, r1);get(y - k + 1, y, l2, r2);if (start == l1) start = l2;else{fuck *p = start;while (p->nex != l1) p = p->nex;p->nex = l2;}r1->nex = r2->nex;r2->nex = l1;maintain();break;}case 5:{scanf("%d%d%d", &x, &y, &val);fuck *l, *r;get(x, y, l, r), r = r->nex;for (fuck *p = l; p != r; p = p->nex)p->ga(val);maintain();break;}case 6:{scanf("%d%d%d", &x, &y, &val);fuck *l, *r;get(x, y, l, r), r = r->nex;for (fuck *p = l; p != r; p = p->nex)p->gc(val);maintain();break;}case 7:{scanf("%d%d", &x, &y);fuck *l, *r;get(x, y, l, r), r = r->nex;long long ans = 0;for (fuck *p = l; p != r; p = p->nex)ans += p->qsum();printf("%lld\n", ans);maintain();break;}case 8:{scanf("%d%d", &x, &y);fuck *l, *r;get(x, y, l, r), r = r->nex;int maxn = 0, minn = 0x7fffffff;for (fuck *p = l; p != r; p = p->nex)chkmax(maxn, p->qmax()), chkmin(minn, p->qmin());printf("%d\n", maxn - minn);maintain();break;}case 9:{scanf("%d%d%d", &x, &y, &val);fuck *l, *r;get(x, y, l, r), r = r->nex;int res = 0x7fffffff;for (fuck *p = l; p != r; p = p->nex)chkmin(res, p->mindis(val));printf("%d\n", res);maintain();break;}case 10:{scanf("%d%d%d", &x, &y, &k);fuck *l, *r;get(x, y, l, r), r = r->nex;long long cl = 1, cr = 0x7fffffff;while (cl < cr){long long mid = (cl + cr) / 2;int tot = 0;for (fuck *p = l; p != r; p = p->nex)tot += p->query(mid);if (tot >= k) cr = mid;else cl = mid + 1;}printf("%lld\n", cl - 1);maintain();break;}case 11:{scanf("%d%d%d", &x, &y, &val);fuck *l, *r;get(x, y, l, r), r = r->nex;int ans = 0;for (fuck *p = l; p != r; p = p->nex)ans += p->query(val);printf("%d\n", ans);maintain();break;}}}del(start);return 0;
}

轉載于:https://www.cnblogs.com/oier/p/10366764.html

總結

以上是生活随笔為你收集整理的[BZOJ3337] ORZJRY I --块状链表大毒瘤的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。