「fzyzoj1969」无敌的妹子2
Description
http://110.90.118.124/OnlineJudge/problem_show.php?id=1969
土豪无敌有很多相机，因为需要秀相机，所以需要拍很多妹纸，现在，无敌招募了n只妹纸，从1到n编号摆在架子上。现在无敌要给妹纸穿各种衣服来增加妹纸的美丽值（由于无敌很正直，他懒得把妹纸的衣服卸下来，只会不停地给妹纸穿衣服（妹纸：热出翔）
他经常会把某个让他很不爽的区间内的妹纸全部替换掉；或者给某个区间内的妹纸都穿上某种衣服。
有时候无敌要试下某个相机，无敌就会随手在架子上的某个区间内找到最美丽的妹纸（一般是XXX）。
有时候会用些镜头歪斜的相机(都是小叶子给搞歪的)拍照，无敌为了防止美丽的妹纸（一般是XXX）生他的气，不敢乱拍美丽的妹纸，就只好随手在架子上的某个区间内找到最ugly的妹纸。
当然，还有时候无敌要给小叶子炫自己的妹纸，就会随手抱出在架子上的某个区间内的妹纸，并计算她们美丽值的和。
Input Format
第一行输入妹纸数n和操作数m
第二行n个数，表示妹纸自身的美丽值ai（这时候还没进行操作）
接下来m行，每行有四个数或五个数，c，dir，ql，qr，(v) (表示询问时，一行只有四个数，表示修改时，一行有五个数)
第一个数c若为1，表示询问：
表示询问时,第二个数dir若为1，表示无敌要对小叶子炫妹子，输出区间[ql,qr]内妹纸美丽值的总和
第二个数dir若为2，表示无敌只能用逗逼的镜头，输出区间[ql,qr]内最ugly的妹纸的美丽值
第二个数dir若为3，表示无敌试相机，输出区间[ql,qr]内最美丽的妹纸的美丽值
第一个数c若为2，表示修改：
第二个数dir若为1，表示无敌要给区间[ql,qr]内的妹纸都穿上一件美丽值为v的衣服
第二个数dir若为2，表示无敌要把区间[ql,qr]内的妹纸全部替换成美丽值为v的妹纸
Output Format
对于每个询问，输出一行对应的信息
Sample Input
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
10 15 27 12 57 80 24 64 96 81 18 45 1 3 9 9 1 1 3 10 1 2 5 7 2 2 1 8 79 1 1 1 4 2 2 5 8 42 2 1 1 5 15 2 1 2 5 72 1 1 2 2 2 1 1 5 35 2 2 10 10 57 1 1 5 5 1 3 5 8 2 1 8 8 78 2 2 5 5 84 |
Sample Output
|
1 2 3 4 5 6 7 |
18 465 24 316 166 164 164 |
Hint
n<=1000000,m<=100000
0<=v,ai<=10000
代码
|
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 |
#include<iostream> #include<cstdlib> #include<cstdio> #define ll long long using namespace std; int n,m; struct data{int l,r,sum,mn,mx,atag,ctag;}t[4000001]; void pushup(int k) { t[k].sum=t[k<<1].sum+t[k<<1|1].sum; t[k].mn=min(t[k<<1].mn,t[k<<1|1].mn); t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx); } void build(int k,int l,int r) { t[k].ctag=-1;t[k].l=l;t[k].r=r; if(l==r){scanf("%d",&t[k].sum);t[k].mn=t[k].mx=t[k].sum;return;} int mid=(l+r)>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); pushup(k); } void pushdown(int k) { int a=t[k].atag,c=t[k].ctag,x=t[k].r-t[k].l+1; if(c!=-1){ t[k<<1].ctag=t[k<<1|1].ctag=c; t[k<<1].atag=t[k<<1|1].atag=0; t[k<<1].sum=c*(x-(x>>1)); t[k<<1|1].sum=c*(x>>1); t[k<<1].mn=t[k<<1|1].mn=t[k<<1].mx=t[k<<1|1].mx=c; t[k].ctag=-1; } if(a!=0){ t[k<<1].atag+=a;t[k<<1|1].atag+=a; t[k<<1].sum+=a*(x-(x>>1));t[k<<1|1].sum+=a*(x>>1); t[k<<1].mn+=a;t[k<<1|1].mn+=a; t[k<<1].mx+=a;t[k<<1|1].mx+=a; t[k].atag=0; } } void change(int k,int x,int y,int z) { pushdown(k); int l=t[k].l,r=t[k].r; if(l==x&&y==r){ if(l!=r)t[k].ctag=z; t[k].mn=t[k].mx=z; t[k].sum=(r-l+1)*z; return;} int mid=(l+r)>>1; if(mid>=y)change(k<<1,x,y,z); else if(mid<x)change(k<<1|1,x,y,z); else { change(k<<1,x,mid,z); change(k<<1|1,mid+1,y,z);} pushup(k); } void add(int k,int x,int y,int z) { pushdown(k); int l=t[k].l,r=t[k].r; if(l==x&&y==r){ if(l!=r)t[k].atag=z; t[k].sum+=(r-l+1)*z; t[k].mn+=z;t[k].mx+=z; return;} int mid=(l+r)>>1; if(mid>=y)add(k<<1,x,y,z); else if(mid<x)add(k<<1|1,x,y,z); else { add(k<<1,x,mid,z); add(k<<1|1,mid+1,y,z); } pushup(k); } int ask(int k,int x,int y,int f) { pushdown(k); int l=t[k].l,r=t[k].r; if(l==x&&r==y) { if(f==1)return t[k].sum; else if(f==2)return t[k].mn; else return t[k].mx; } int mid=(l+r)>>1; if(mid>=y)return ask(k<<1,x,y,f); else if(mid<x)return ask(k<<1|1,x,y,f); else { if(f==1)return (ask(k<<1,x,mid,f)+ask(k<<1|1,mid+1,y,f)); else if(f==2)return min(ask(k<<1,x,mid,f),ask(k<<1|1,mid+1,y,f)); else return max(ask(k<<1,x,mid,f),ask(k<<1|1,mid+1,y,f)); } } int main() { scanf("%d%d",&n,&m); build(1,1,n); for(int i=1;i<=m;i++) { int c,dir,x,y,v; scanf("%d",&c); if(c==1){scanf("%d%d%d",&dir,&x,&y);printf("%d\n",ask(1,x,y,dir));} else { scanf("%d%d%d%d",&dir,&x,&y,&v); if(dir==1)add(1,x,y,v); else change(1,x,y,v); } } return 0; } |
Subscribe
计数器 9720256
OI 课件=>
OI 课件=>