BZOJ 3878: [Ahoi2014]奇怪的计算器
正文索引 [隐藏]
Description
【故事背景】
JYY有个奇怪的计算器，有一天这个计算器坏了，JYY希望你能帮助他写
一个程序来模拟这个计算器的运算。
【问题描述】
JYY的计算器可以执行N条预设好的指令。每次JYY向计算器输入一个正
整数X，计算器就会以X作为初始值，接着依次执行预设的N条指令，最后把
最终得出的结果返回给JYY。
每一条指令可以是以下四种指令之一：（这里a表示一个正整数。）
1、+a：表示将当前的结果加上a；
2、-a：表示将当前的结果减去a；
3、a：表示将当前的结果乘以a；
4、@a：表示将当前的结果加上aX（X是一开始JYY输入的数）。
计算器用于记录运算结果的变量的存储范围是有限的，所以每次运算结束之
后会有计算结果溢出的问题。
JYY的计算器中，存储每计算结果的变量只能存储L到R之间的正整数，
如果一次指令执行过后，计算结果超过了R，那么计算器就会自动把结果变成R，然后再以R作为当前结果继续进行之后的计算。同理，如果运算结果小于L，计算器也会把结果变成L，再接着计算。
比如，假设计算器可以存储1到6之间的值，如果当前的计算结果是2，那
么在执行+5操作之后，存储结果的变量中的值将会是6。虽然2+5的实际结
果是7，但是由于7超过了存储范围的上界，所以结果就被自动更正成了上界的大小，也就是6。
JYY一共想在计算器上输入Q个值，他想知道这Q个值输入计算器之后，
分别会得到什么结果呢？
Input
输入文件的第一行包含三个正整数，N，L和R；
第接下来N行，每行一个指令，每个指令如题述，由一个字符和一个正整
数组成，字符和正整数中间有一个空格隔开；
第N+2行包含一个整数Q，表示JYY希望输入的数的数量；
第接下来Q行每行一个正整数，第k个正整数Xk表示JYY在第k次输入的
整数。
Output
输出Q行每行一个正整数，第k行的整数表示输入Xk后，依次经过N个指
令进行计算所得到的结果。
Sample Input
5 1 6
+ 5
- 3
* 2
- 7
@ 2
3
2
1
5
Sample Output
5
3
6
HINT
【样例说明】
当JYY输入2时，计算器会进行5次运算，每一次运算之后得到的结果分
别是6（实际计算结果为7但是超过了上界），3，6，1（实际结果为-1但是低于了下界）和5（由于一开始输入的是2，所以这一次计算为1+2×2）。
1<=N,Q<=10^5,1<=L<=Xk<=R<=10^9,1<=a<=10^9
题解
这道题目一看就觉得束手无策，我去年直接暴力Orz、、、、、
其实算法是线段树，为什么呢，因为线段树可以区间操作 & Lazy Tag呀！
我们首先发现把所有数字一起做，一旦用了Lazy Tag就可以减少计算了。
继续发现，这个序列如果初始状态是有序的，那么无论怎么操作，最终都是有序的！
这样一来我们就可以啪啪啪的线段树维护操作，然后超出范围的直接强行Tag赋值【因为必然是最左一段和最右一端
代码
|
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 |
/*Author:WNJXYK*/ #include<cstdio> #include<algorithm> using namespace std; int n,q; long long L,R; struct Calc{ int type; long long num; }; Calc calc[100005]; struct Que{ long long num; int index; }; Que que[100005]; bool cmp(Que a,Que b){ if (a.num<b.num) return true; if (a.num==b.num && a.index<b.index) return true; return false; } long long ans[100005]; struct Btree{ int left,right; long long num; long long anum; long long min,max; long long amin,amax; long long vt; long long pt,tt; long long at; }; Btree tree[400005]; inline long long remax(long long a,long long b){ if (a>b) return a; return b; } inline long long remin(long long a,long long b){ if (a<b) return a; return b; } void build(int x,int left,int right); void clean(int x); void update(int x); void solvep(int x,long long val); void solvet(int x,long long val); void solvev(int x,long long val); void solvea(int x,long long val); void setvt(int x,long long val); void plus(int x,int left,int right,long long val); void times(int x,int left,int right,long long val); void aplus(int x,int left,int right,long long val); long long query(int x,int pos); void build(int x,int left,int right){ tree[x].left=left;tree[x].right=right; tree[x].vt=tree[x].pt=tree[x].at=0;tree[x].tt=1; if (left==right){ tree[x].num=tree[x].anum=tree[x].min=tree[x].amin=tree[x].max=tree[x].amax=que[left].num; }else{ int mid=(left+right)/2; build(x*2,left,mid); build(x*2+1,mid+1,right); update(x); } } inline void update(int x){ if (tree[x].left==tree[x].right) return; tree[x].max=remax(tree[x*2].max,tree[x*2+1].max); tree[x].min=remin(tree[x*2].min,tree[x*2+1].min); tree[x].amax=remax(tree[x*2].amax,tree[x*2+1].amax); tree[x].amin=remin(tree[x*2].amin,tree[x*2+1].amin); } inline void clean(int x){ if (tree[x].left==tree[x].right) return; int left=x*2,right=x*2+1; if (tree[x].vt!=0){ solvev(left,tree[x].vt);solvev(right,tree[x].vt); tree[x].vt=0; } solvet(left,tree[x].tt);solvet(right,tree[x].tt); tree[x].tt=1; solvep(left,tree[x].pt);solvep(right,tree[x].pt); tree[x].pt=0; solvea(left,tree[x].at);solvea(right,tree[x].at); tree[x].at=0; } inline void solvep(int x,long long val){ tree[x].max+=val;tree[x].min+=val;tree[x].num+=val; tree[x].pt+=val; } inline void solvet(int x,long long val){ tree[x].max*=val;tree[x].min*=val;tree[x].num*=val; tree[x].tt*=val;tree[x].pt*=val; } inline void solvev(int x,long long val){ tree[x].max=tree[x].min=tree[x].num=val; tree[x].vt=val; tree[x].pt=tree[x].at=0;tree[x].tt=1; } inline void solvea(int x,long long val){ tree[x].max+=tree[x].amax*val; tree[x].min+=tree[x].amin*val; tree[x].num+=tree[x].anum*val; tree[x].at+=val; } inline void setvt(int x,long long val){ tree[x].num=tree[x].max=tree[x].min=val; tree[x].vt=val; tree[x].pt=tree[x].at=0;tree[x].tt=1; } inline void plus(int x,int left,int right,long long val){ clean(x); if (left<=tree[x].left && tree[x].right<=right){ if (L<tree[x].min+val && tree[x].max+val<R){ solvep(x,val); }else{ if (tree[x].min+val>=R) setvt(x,R); else if (tree[x].max+val<=L) setvt(x,L); else{ if (tree[x].left==tree[x].right){ solvep(x,val); if (tree[x].num>R) setvt(x,R); if (tree[x].num<L) setvt(x,L); if (tree[x].pt>R) tree[x].pt=R; }else{ int mid=(tree[x].left+tree[x].right)/2; if (left<=mid) plus(x*2,left,right,val); if (mid+1<=right) plus(x*2+1,left,right,val); update(x); } } } }else{ int mid=(tree[x].left+tree[x].right)/2; if (left<=mid) plus(x*2,left,right,val); if (mid+1<=right) plus(x*2+1,left,right,val); update(x); } } inline void times(int x,int left,int right,long long val){ clean(x); if (left<=tree[x].left && tree[x].right<=right){ if (L<tree[x].min*val && tree[x].max*val<R){ solvet(x,val); }else{ if (tree[x].min*val>=R) setvt(x,R); else{ if (tree[x].left==tree[x].right){ solvet(x,val); if (tree[x].num>R) setvt(x,R); if (tree[x].tt>R) tree[x].tt=R; }else{ int mid=(tree[x].left+tree[x].right)/2; if (left<=mid) times(x*2,left,right,val); if (mid+1<=right) times(x*2+1,left,right,val); update(x); } } } }else{ int mid=(tree[x].left+tree[x].right)/2; if (left<=mid) times(x*2,left,right,val); if (mid+1<=right) times(x*2+1,left,right,val); update(x); } } inline void aplus(int x,int left,int right,long long val){ clean(x); if (left<=tree[x].left && tree[x].right<=right){ if (L<tree[x].min+val*tree[x].amin && tree[x].max+val*tree[x].amax<R){ solvea(x,val); }else{ if (tree[x].min+val*tree[x].amin>=R) setvt(x,R); else if (tree[x].max+val*tree[x].amax<=L) setvt(x,L); else{ if (tree[x].left==tree[x].right){ solvea(x,val); if (tree[x].num>R) setvt(x,R); if (tree[x].num<L) setvt(x,L); if (tree[x].at>R) tree[x].at=R; }else{ int mid=(tree[x].left+tree[x].right)/2; if (left<=mid) aplus(x*2,left,right,val); if (mid+1<=right) aplus(x*2+1,left,right,val); update(x); } } } }else{ int mid=(tree[x].left+tree[x].right)/2; if (left<=mid) aplus(x*2,left,right,val); if (mid+1<=right) aplus(x*2+1,left,right,val); update(x); } } long long query(int x,int pos){ clean(x); if (tree[x].left==tree[x].right && tree[x].left==pos){ return tree[x].num; }else{ int mid=(tree[x].left+tree[x].right)/2; if (pos<=mid) return query(x*2,pos); if (mid+1<=pos) return query(x*2+1,pos); } } inline int read(){ char x=getchar(); while(x!='+' && x!='-' && x!='*' && x!='@') x=getchar(); if (x=='+') return 1; if (x=='-') return 2; if (x=='*') return 3; if (x=='@') return 4; } int main(){ //freopen("calc.in","r",stdin); //freopen("calc.out","w",stdout); scanf("%d%lld%lld",&n,&L,&R); for (int i=1;i<=n;i++){ calc[i].type=read(); scanf("%lld",&calc[i].num); } scanf("%d",&q); for (int i=1;i<=q;i++){ scanf("%lld",&que[i].num); que[i].index=i; } sort(que+1,que+q+1,cmp); build(1,1,q); for (int i=1;i<=n;i++){ if (calc[i].type==1)plus(1,1,q,calc[i].num); if (calc[i].type==2)plus(1,1,q,-calc[i].num); if (calc[i].type==3)times(1,1,q,calc[i].num); if (calc[i].type==4)aplus(1,1,q,calc[i].num); } for (int i=1;i<=q;i++)ans[que[i].index]=query(1,i); for (int i=1;i<=q;i++)printf("%lldn",ans[i]); return 0; } |
[fire]数据下载：链接：http://pan.baidu.com/s/1ntso8dj 密码：6v6p[/fire]
原文链接：BZOJ 3878: [Ahoi2014]奇怪的计算器
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!