首页 > 代码库 > 【BZOJ-3337】ORZJRY I 块状链表
【BZOJ-3337】ORZJRY I 块状链表
3337: ORZJRY I
Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 190 Solved: 50
[Submit][Status][Discuss]
Description
Jry最近做(屠)了很多数据结构题，所以想 BS你，他希望你能实现一种数据结构维护一个序列：
Input
第一行n；
第二行n个数；
第三行q，代表询问个数；
接下来q行，每行一个op，输入格式见描述。
Output
对于7≤op≤11的操作，一行输出一个答案。
Sample Input
6
5 2 6 3 1 4
15
7 2 4
8 1 3
9 2 4 5
10 1 6 4
11 2 5 4
6 1 4 7
8 1 4
5 3 4 5
2 1
1 2 8
3 3 5
4 1 5 2
9 2 5 4
10 3 6 4
11 1 6 100
5 2 6 3 1 4
15
7 2 4
8 1 3
9 2 4 5
10 1 6 4
11 2 5 4
6 1 4 7
8 1 4
5 3 4 5
2 1
1 2 8
3 3 5
4 1 5 2
9 2 5 4
10 3 6 4
11 1 6 100
Sample Output
11
4
1
4
3
0
3
12
6
4
1
4
3
0
3
12
6
HINT
n,q≤100000；
任意时刻数列中的数≤2^31-1。
0≤任意时刻数列中的数≤2^31-1。
本题共3组数据
Source
by orzjry
Solution
switch(opt)
{
case 1: 直接分裂后插入即可 break;
case 2: 分裂后直接删除 break;
case 3: 分裂得到[l,r]将指向l的块指向r，l指向r指向的块，然后给[l,r]中所有块打上反转标记 break;
case 4: 提取出[r-k,r]，将这段从中删除，再整段插入到l之前 break;
case 5: 提取[l,r]，打tag标记 break;
case 6: 提取[l,r]，打del标记 break;
case 7: 提取[l,r]，扫描一遍区间中的所有块，统计sum break;
case 8: 同上，统计max和min，输出max-min break;
case 9: 想的还是需要二分，但还没有特别精妙的想法 break;
case 10: 对每个块额外记录一个排序后的数列，然后找K小 break;
case 11: 对每个块额外处理一个有序的数列，然后二分统计个数 break;
}
上述这些二分大都可以用STL中的替代，注意的是Split和Merge的时候要PushDown和Update
Code
#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>using namespace std;int read(){ int x=0,f=1; char ch=getchar(); while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();} while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();} return x*f;}namespace BlockLists{ #define BN struct BLNode{int next,from,data[],tmp[],size; int maxx,minn,tag,sum; bool rev;}B[BN]; queue<int>trash; inline int New() {if (trash.empty()) return ++sz; int tmp=trash.front(); trash.pop(); return tmp;} inline void Del(int x) {trash.push(x); B[x].next=-1; B[x].size=B[x].maxx=B[x].minn=B[x].sum=B[x].tag=B[x].rev=0;} inline int GetP(int rk) {for (int i=start; ~i; i=B[i].next) if (rk>B[i].size) rk-=B[i].size; else return i;} inline int GetK(int rk) {for (int i=start; ~i; i=B[i].next) if (rk>B[i].size) rk-=B[i].size; else return rk;} inline void Data(int pos,int len,int data[],int suf) {B[pos].next=suf; B[pos].size=len; memcpy(B[pos].data,data,len);} inline void PushDown(int x) { int sz=B[x].size; if (B[x].del) {int del=B[x].del; B[x].del=0; for (int i=0; i<sz; i++) B[x].data[i]=del; B[x].sum=sz*del; B[x].maxx=B[x].minn=del;} if (B[x].rev) {reverse(B[x].data,B[x].data+sz);} if (B[x].tag) {int tag=B[x].tag; B[x].tag=0; for (int i=0; i<sz; i++) B[x].data[i]+=tag; B[x].sum+=sz*tag; B[x].maxx+=tag; B[x].minn+=tag;} } inline void Update(int x) { int sz=B[x].size; B[x].sum=0; for (int i=0; i<sz; i++) B[x].sum+=B[x].data[i]; memcpy(B[x].tmp,B[x].data,sz); sort(B[x].tmp,B[x].tmp+sz); } inline void Split(int pos,int rk) { PushDown(pos); if (B[pos]==rk) return; int id=New(); Data(id,B[pos].size-rk,B[pos].data+rk,B[pos].next); B[pos].next=id; B[pos].size=rk; Update(id); Update(pos); } inline void Merge(int pos) { for ( ; ~pos; pos=B[pos].next) for (int suf=B[pos].next; ~suf && B[pos].size+B[suf].size<Bsize; suf=B[suf].next) PushDown(pos),PushDown(suf), memcpy(B[pos].data+B[pos].size,B[suf].data,B[suf].size),B[pos].next=B[suf].next,B[pos].size+=B[suf].size, Del(suf),Update(pos); } inline void Insert(int s) { int now=GetP(s),pos=GetK(s); Split(now,pos); int id=New(); Data(id,1,a+1,B[now].next); B[now].next=id; Merge(now); } inline void Delete(int s) { int now=GetP(s),pos=GetK(s); Split(now,pos); Del(B[pos].next); Merge(now); } inline void Prework(int l,int r,int &x,int &y) { int now1=GetP(l),pos1=GetK(l); Split(now1,pos1); int now2=GetP(r),pos2=GetK(r); Split(now2,pos2); x=pos1,y=pos2; } inline void Rever() { } inline void Change() inline void Move() inline void Add() inline void Modify() inline void GetSum() inline void GetRange() inline void GetClose() inline void GetKth() inline void GetSmall()}using namespace BlockLists;int main(){ int N=read(); for (int i=1; i<=N; i++) a[0]=read(),Insert(i-1); Bsize=ceil(sqrt(N)); Q=read(); while (Q--) { int opt=read(); int x,y,k,val; switch (opt) { case 1: x=read()-1,val=read(),Change(x,val); break; case 2: x=read()-1; Delete(x); break; case 3: x=read()-1,y=read()-1; Rever(x,y); break; case 4: x=read()-1,y=read()-1,k=read(); Move(x,y); break; case 5: x=read()-1,y=read()-1; val=read(); Add(x,y,val); break; case 6: x=read()-1,y=read()-1; val=read(); Modify(x,y,val); break; case 7: x=read()-1,y=read()-1; GetSum(x,y); break; case 8: x=read()-1,y=read()-1; GetRange(x,y); break; case 9: x=read()-1,y=read()-1; GetClose(x,y); break; case 10: x=read()-1,y=read()-1,k=read(); GetKth(x,y,k); break; case 11: x=read()-1,y=read()-1,val=read(); GetSmall(x,y,val); break; } } return 0;}
【BZOJ-3337】ORZJRY I 块状链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。