感觉树套树是个非常高深的数据结构。从来没写过
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <vector> 6 #define LL long long 7 using namespace std; 8 const LL Maxm=50100; 9 const LL Maxn=50100; 10 const LL T=300; 11 struct OPERATOR 12 { 13 LL Type,a,b,c; 14 }Operator[Maxm]; 15 LL Sum[Maxn*T],ls[Maxn*T],rs[Maxn*T],Addv[Maxn*T],sz=0,V[Maxm],Root[Maxn*6]; 16 LL n,m,H; 17 inline void Get_Int(LL &x) 18 { 19 x=0; register char ch=getchar(); LL f=1; 20 while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();} 21 while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} x*=f; 22 } 23 inline void Put_Int(LL x) 24 { 25 char ch[20]; register int top=0; 26 if (x==0) ch[++top]='0'; 27 while (x) ch[++top]=x%10+'0',x/=10; 28 while (top) putchar(ch[top--]); putchar(' '); 29 } 30 //================================================================= 31 inline void Push_Down(LL o,LL p,LL q) 32 { 33 if (!ls[o]) ls[o]=++sz; 34 if (!rs[o]) rs[o]=++sz; 35 LL l=ls[o],r=rs[o]; 36 if (Addv[o]) 37 { 38 Addv[l]+=Addv[o]; 39 Addv[r]+=Addv[o]; 40 LL mid=(p+q)>>1; 41 Sum[l]+=(mid-p+1)*Addv[o]; 42 Sum[r]+=(q-mid)*Addv[o]; 43 Addv[o]=0; 44 } 45 } 46 inline void Push_Up(LL o) {Sum[o]=Sum[ls[o]]+Sum[rs[o]];} 47 void Add_Num(LL &o,LL l,LL r,LL p,LL q) 48 { 49 if (o==0) o=++sz; 50 if (l==p && r==q) 51 { 52 Sum[o]+=(q-p+1); 53 Addv[o]++; 54 return; 55 } 56 Push_Down(o,l,r); 57 LL mid=(l+r)>>1; 58 if (q<=mid) Add_Num(ls[o],l,mid,p,q); 59 if (p>=mid+1) Add_Num(rs[o],mid+1,r,p,q); 60 if (p<=mid && q>=mid+1) 61 Add_Num(ls[o],l,mid,p,mid),Add_Num(rs[o],mid+1,r,mid+1,q); 62 Push_Up(o); 63 } 64 void Update(LL o,LL l,LL r,LL p,LL q,LL c) 65 { 66 Add_Num(Root[o],1,n,p,q); 67 if (l==r) return; 68 LL mid=(l+r)>>1; 69 if (c<=mid) Update(o<<1,l,mid,p,q,c); 70 if (c>=mid+1) Update(o<<1|1,mid+1,r,p,q,c); 71 } 72 //======================================== 73 74 LL Get_Sum(LL o,LL l,LL r,LL p,LL q) 75 { 76 if (!o) return 0; 77 if (p==l && r==q) return Sum[o]; 78 LL mid=(l+r)>>1; 79 Push_Down(o,l,r); 80 if (q<=mid) return Get_Sum(ls[o],l,mid,p,q); 81 if (p>=mid+1) return Get_Sum(rs[o],mid+1,r,p,q); 82 if (p<=mid && q>=mid+1) return Get_Sum(ls[o],l,mid,p,mid)+Get_Sum(rs[o],mid+1,r,mid+1,q); 83 } 84 85 86 LL Query(LL o,LL l,LL r,LL p,LL q,LL k) 87 { 88 LL ret=Get_Sum(Root[o<<1],1,n,p,q); 89 if (l==r) return l; 90 LL mid=(l+r)>>1; 91 if (k<=ret) return Query(o<<1,l,mid,p,q,k); 92 if (k>=ret+1) return Query(o<<1|1,mid+1,r,p,q,k-ret); 93 } 94 95 int main() 96 { 97 Get_Int(n),Get_Int(m); LL cnt=0; 98 for (int i=1;i<=m;i++) 99 { 100 Get_Int(Operator[i].Type); 101 Get_Int(Operator[i].a),Get_Int(Operator[i].b),Get_Int(Operator[i].c); 102 if (Operator[i].Type==1) V[++cnt]=Operator[i].c; 103 } 104 sort(V+1,V+cnt+1); 105 H=unique(V+1,V+cnt+1)-(V+1); 106 for (int i=1;i<=m;i++) 107 { 108 if (Operator[i].Type==1) Update(1,1,H,Operator[i].a,Operator[i].b,H-(lower_bound(V+1,V+H+1,Operator[i].c)-V)+1); 109 if (Operator[i].Type==2) Put_Int(V[H-Query(1,1,H,Operator[i].a,Operator[i].b,Operator[i].c)+1]); 110 } 111 return 0; 112 }
加了标记永久化以后
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <vector> 6 #define LL long long 7 using namespace std; 8 const LL Maxm=50100; 9 const LL Maxn=50100; 10 const LL T=300; 11 struct OPERATOR 12 { 13 LL Type,a,b,c; 14 }Operator[Maxm]; 15 LL Sum[Maxn*T],ls[Maxn*T],rs[Maxn*T],Addv[Maxn*T],sz=0,V[Maxm],Root[Maxn*6]; 16 LL n,m,H; 17 inline void Get_Int(LL &x) 18 { 19 x=0; register char ch=getchar(); LL f=1; 20 while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();} 21 while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} x*=f; 22 } 23 inline void Put_Int(LL x) 24 { 25 char ch[20]; register int top=0; 26 if (x==0) ch[++top]='0'; 27 while (x) ch[++top]=x%10+'0',x/=10; 28 while (top) putchar(ch[top--]); putchar(' '); 29 } 30 //================================================================= 31 void Add_Num(LL &o,LL l,LL r,LL p,LL q) 32 { 33 if (o==0) o=++sz; 34 Sum[o]+=(q-p+1); 35 if (l==p && r==q) 36 { 37 Addv[o]++; 38 return; 39 } 40 if (!ls[o]) ls[o]=++sz; 41 if (!rs[o]) rs[o]=++sz; 42 LL mid=(l+r)>>1; 43 if (q<=mid) Add_Num(ls[o],l,mid,p,q); 44 if (p>=mid+1) Add_Num(rs[o],mid+1,r,p,q); 45 if (p<=mid && q>=mid+1) 46 Add_Num(ls[o],l,mid,p,mid),Add_Num(rs[o],mid+1,r,mid+1,q); 47 } 48 void Update(LL o,LL l,LL r,LL p,LL q,LL c) 49 { 50 Add_Num(Root[o],1,n,p,q); 51 if (l==r) return; 52 LL mid=(l+r)>>1; 53 if (c<=mid) Update(o<<1,l,mid,p,q,c); 54 if (c>=mid+1) Update(o<<1|1,mid+1,r,p,q,c); 55 } 56 //======================================== 57 58 LL Get_Sum(LL o,LL l,LL r,LL p,LL q,LL pos) 59 { 60 if (!o) return 0; 61 if (p==l && r==q) return Sum[o]+pos*(r-l+1); 62 LL mid=(l+r)>>1; 63 if (!ls[o]) ls[o]=++sz; 64 if (!rs[o]) rs[o]=++sz; 65 if (q<=mid) return Get_Sum(ls[o],l,mid,p,q,pos+Addv[o]); 66 if (p>=mid+1) return Get_Sum(rs[o],mid+1,r,p,q,pos+Addv[o]); 67 if (p<=mid && q>=mid+1) return Get_Sum(ls[o],l,mid,p,mid,pos+Addv[o])+Get_Sum(rs[o],mid+1,r,mid+1,q,pos+Addv[o]); 68 } 69 70 71 LL Query(LL o,LL l,LL r,LL p,LL q,LL k) 72 { 73 LL ret=Get_Sum(Root[o<<1],1,n,p,q,0); 74 if (l==r) return l; 75 LL mid=(l+r)>>1; 76 if (k<=ret) return Query(o<<1,l,mid,p,q,k); 77 if (k>=ret+1) return Query(o<<1|1,mid+1,r,p,q,k-ret); 78 } 79 80 int main() 81 { 82 // freopen("sequence.in","r",stdin); 83 // freopen("sequence.out","w",stdout); 84 Get_Int(n),Get_Int(m); LL cnt=0; 85 for (int i=1;i<=m;i++) 86 { 87 Get_Int(Operator[i].Type); 88 Get_Int(Operator[i].a),Get_Int(Operator[i].b),Get_Int(Operator[i].c); 89 if (Operator[i].Type==1) V[++cnt]=Operator[i].c; 90 } 91 sort(V+1,V+cnt+1); 92 H=unique(V+1,V+cnt+1)-(V+1); 93 for (int i=1;i<=m;i++) 94 { 95 if (Operator[i].Type==1) Update(1,1,H,Operator[i].a,Operator[i].b,H-(lower_bound(V+1,V+H+1,Operator[i].c)-V)+1); 96 if (Operator[i].Type==2) Put_Int(V[H-Query(1,1,H,Operator[i].a,Operator[i].b,Operator[i].c)+1]); 97 } 98 return 0; 99 }
直接20s卡时，加了标记永久化之后18s，还是很慢！