YZOJ P2319 宇宙图书馆
时间限制:1000MS 内存限制:131072KB
难度: \(3.4\)
-
题目描述
宇宙图书馆(Universal Library)是一个规模巨大的图书馆,该图书馆收集各个星球出版的大量系列图书。为了统一时间,宇宙图书馆的每本书的出版年份以 “宇宙年” 为单位来记录。当然,尽管图书馆可以存非常多的书,但书不能无休止地增加,因此管理员会定期剔除出版年份小于某个数的所有书。
由于书的数量多,无法手工统计,你需要编写一个图书管理系统,来管理宇宙图书馆的图书记录。
-
输入格式
第一行为一个正整数 \(N\),为该系统设定的出版年份上限(单位:宇宙年,之后涉及的所有出版年份均为 \(1\) 到 \(N\) 之间的正整数。
之后,每行一个合法的命令,命令有以下五种:
Add t x
:添加一套共 \(x\) 本书(\(x\) 为正整数),这一套书的出版年份均为 \(t\)(单位:宇宙年);
Remove t
:删除所有出版年份小于 \(t\) (单位:宇宙年)的书,并输出被删除的书的数量;
Count a b
:统计出版年份(单位:宇宙年)在 \(a, b\) 之间(含 \(a, b\),保证 \(a \leq b\) )的书的数量,并输出;
List x
:将所有书按出版年份从大到小(也就是从新到旧)顺序列出,但由于输出可能较多,这里只要求输出列表中给定的第 \(x\) 本书的出版年份(如果不存在,输出 No
);
Quit
:退出系统,结束程序。
-
输出格式
对每个 Remove、Count、List
命令,输出一行答案。
-
样例输入
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
15 Add 10 3 Add 8 2 Add 9 1 Count 9 10 Count 8 10 List 3 List 1 List 4 Remove 8 List 5 List 6 Count 8 9 Remove 9 List 5 Count 8 9 Add 1 20 Add 15 13 Add 15 14 Count 1 15 Count 2 15 List 18 Quit |
-
样例输出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
4 6 10 10 9 0 8 8 3 2 No 1 51 31 15 |
-
数据规模与约定
水题,详细的范围就不贴了
保证 \(1 \leq N, \) 总操作次数 \( \leq 100,000\) ,计算过程中出现的数保证不超过 \(10^9\) 。
线段树裸题?
没错就是线段树裸题,不知道为什么我考场上写了个 \(O(Nlog^2N)\) 的。。。。
把年份拿去开一棵线段树,Add
就是单点修改,Remove
就是区间修改,Count
就是区间查询,就是这个 List
有点东西。
考虑一下怎么求线段树中第 \(k\) 本书的位置。
首先考虑这样一个线段树,F 为父节点,Ls、Rs 分别为左右子节点。
因为是线段树,所以考虑递归查找对于父节点来说第 \(k\) 本书的位置。
很显然有下面两种情况:
如果左子节点中,书的数量不比 \(k\) 小,那么第 \(k\) 本书一定在左子节点中,并且对于左子节点来说要查找的也是第 \(k\) 本书。
如果左子节点中,书的数量比 \(k\) 小,那么第 \(k\) 本书一定在右子节点中,但是对于右子节点来说要查找的就变为第 \(k – sum_{Ls}\) 本书了(\(sum_{Ls}\) 表示左子节点书的数量)。
要是 \(k\) 比当前所有书总量还多,那就是 No
了。
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 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> inline int getnum() { register char c=getchar(); while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') { a*=10;a+=c-'0'; c=getchar(); } return a; } inline char getchr() { register char c=getchar(); while(!(c>='A' && c<='Z')) c=getchar(); return c; } int sum[105050<<2]; bool tag[105050<<2]; #define Ls(o) (o<<1) #define Rs(o) (o<<1|1) inline void PushDownTree(register int O) { if(!tag[O]) return; tag[O]=false; tag[Ls(O)]=tag[Rs(O)]=true; sum[Ls(O)]=sum[Rs(O)]=0; } inline void PushUpTree(register int O) { sum[O]=sum[Ls(O)]+sum[Rs(O)]; } int QL,QR; int QueryTree(register int O,register int L,register int R) { if(QL<=L && QR>=R) return sum[O]; PushDownTree(O); register int mid=(L+R)>>1,ans=0; if(QL<=mid) ans+=QueryTree(Ls(O),L,mid); if(mid<QR) ans+=QueryTree(Rs(O),mid+1,R); return ans; } int MP,MV; void ModifyTreeNode(register int O,register int L,register int R) { if(L==R) { sum[O]+=MV; return; } PushDownTree(O); register int mid=(L+R)>>1; if(MP<=mid) ModifyTreeNode(Ls(O),L,mid); else ModifyTreeNode(Rs(O),mid+1,R); PushUpTree(O); } int ML,MR; void ModifyTreeSegment(register int O,register int L,register int R) { if(ML<=L && MR>=R) { tag[O]=true,sum[O]=0; return; } PushDownTree(O); register int mid=(L+R)>>1; if(ML<=mid) ModifyTreeSegment(Ls(O),L,mid); if(mid<MR) ModifyTreeSegment(Rs(O),mid+1,R); PushUpTree(O); } void SearchTree(register int O,register int L,register int R,register int kth) { if(L==R) { printf("%d\n",L); return; } PushDownTree(O); register int mid=(L+R)>>1; if(sum[Rs(O)]>=kth) SearchTree(Rs(O),mid+1,R,kth); else SearchTree(Ls(O),L,mid,kth-sum[Rs(O)]); } int main() { register int N=getnum(); while(1) { char c=getchr(); if(c=='Q') break; else if(c=='A') { MP=getnum(),MV=getnum(); ModifyTreeNode(1,1,N); } else if(c=='R') { ML=1,MR=getnum()-1; QL=ML,QR=MR; if(QL<=QR) { printf("%d\n",QueryTree(1,1,N)); ModifyTreeSegment(1,1,N); } else printf("0\n"); } else if(c=='C') { QL=getnum(),QR=getnum(); printf("%d\n",QueryTree(1,1,N)); } else if(c=='L') { register int x=getnum(); if(x>sum[1]) printf("No\n"); else SearchTree(1,1,N,x); } } return 0; } |