| 记录编号 |
449849 |
评测结果 |
AAAAAAAAAAA |
| 题目名称 |
快速红包变换 |
最终得分 |
100 |
| 用户昵称 |
 FoolMike |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
2.380 s |
| 提交时间 |
2017-09-15 11:06:29 |
内存使用 |
13.17 MiB |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int read(){
int x=0;bool sign=0;char ch=getchar();
while ((ch>'9'||ch<'0')&&ch!='-') ch=getchar();
if (ch=='-') sign=1,ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return sign?-x:x;
}
void print(int x){
if (!x) return (void)puts("0");
if (x<0) putchar('-'),x=-x;
static char str[20]="";
int len=0;
for (;x;x/=10) str[++len]=x%10;
while (len) putchar(str[len--]+'0');
putchar('\n');
}
const int inf=1e9;
struct pr{int first,second;};
void merge_max(pr &x,pr y){
if (y.first>x.first) x=y;else
if (y.first==x.first) x.second+=y.second;
}
void merge_min(pr &x,pr y){
if (y.first<x.first) x=y;else
if (y.first==x.first) x.second+=y.second;
}
const int N=1e5+10;
int n,m,a[N],blo[N];
int block_size,num_block;
bool cmp(int x,int y){return a[x]<a[y];}
struct node{
int val,cnt;
node *pre,*nxt;
void init(int Val,int Cnt){val=Val;cnt=Cnt;pre=nxt=0;}
}*Q[N];
struct block_array{
int l,r,q[1010],pos,tag,sum;
node *head,*tail;
void link_to_array(){
int p=1;
for (node *i=head;i;i=i->nxt)
for (int j=0;j<i->cnt;j++) a[q[p++]]=i->val+tag;
}
void array_to_link(){
tag=sum=0;
for (int i=l;i<=r;i++) sum+=a[i];
int pt=l;
(head=tail=Q[pt++])->init(a[q[1]],1);
for (int i=2;i<=pos;i++)
if (a[q[i]]==a[q[i-1]]) tail->cnt++;
else{
node *p;
(p=Q[pt++])->init(a[q[i]],1);
p->pre=tail;
tail=tail->nxt=p;
}
}
void init(int L,int R){
l=L;r=min(R,n);
for (int i=l;i<=r;i++){
q[++pos]=i;
blo[i]=num_block;
Q[i]=new node();
}
sort(q+1,q+pos+1,cmp);
array_to_link();
}
int q1[1010],q2[1010],cq1,cq2;
void rebuild(int L,int R){
cq1=cq2=0;
for (int i=1;i<=pos;i++)
if (L<=q[i]&&q[i]<=R) q1[++cq1]=q[i];
else q2[++cq2]=q[i];
pos=0;
int i=1,j=1;
while (i<=cq1&&j<=cq2) q[++pos]=(a[q1[i]]<a[q2[j]]?q1[i++]:q2[j++]);
for (;i<=cq1;q[++pos]=q1[i++]);
for (;j<=cq2;q[++pos]=q2[j++]);
array_to_link();
}
void makesame(int d){
(head=tail=Q[l])->init(d,pos);
tag=0;sum=d*pos;
}
void add(int L,int R,int d){
if (l>=L&&r<=R){tag+=d;sum+=d*pos;return;}
link_to_array();
L=max(L,l);R=min(R,r);
for (int i=L;i<=R;i++) a[i]+=d;
rebuild(L,R);
}
void makesame(int L,int R,int d){
if (l>=L&&r<=R) return makesame(d);
link_to_array();
L=max(L,l);R=min(R,r);
for (int i=L;i<=R;i++) a[i]=d;
rebuild(L,R);
}
void cbmax(int L,int R,int v){
if (l>=L&&r<=R){
if (v>=tail->val+tag) return makesame(v);
if (head->val+tag>=v) return;
sum+=head->cnt*(v-head->val-tag);
head->val=v-tag;
for (node *i=head->nxt;i&&i->val+tag<=v;i=head->nxt=i->nxt){
sum+=i->cnt*(v-i->val-tag);
head->cnt+=i->cnt;
}
head->nxt->pre=head;
return;
}
link_to_array();
L=max(L,l);R=min(R,r);
for (int i=L;i<=R;i++) a[i]=max(a[i],v);
rebuild(L,R);
}
void cbmin(int L,int R,int v){
if (l>=L&&r<=R){
if (v<=head->val+tag) return makesame(v);
if (tail->val+tag<=v) return;
sum+=tail->cnt*(v-tail->val-tag);
tail->val=v-tag;
for (node *i=tail->pre;i&&i->val+tag>=v;i=tail->pre=i->pre){
sum+=i->cnt*(v-i->val-tag);
tail->cnt+=i->cnt;
}
tail->pre->nxt=tail;
return;
}
link_to_array();
L=max(L,l);R=min(R,r);
for (int i=L;i<=R;i++) a[i]=min(a[i],v);
rebuild(L,R);
}
int qsum(int L,int R){
if (l>=L&&r<=R) return sum;
link_to_array();
int ans=0;
L=max(L,l);R=min(R,r);
for (int i=L;i<=R;i++) ans+=a[i];
return ans;
}
int qwmax(int L,int R){
if (l>=L&&r<=R) return tail->val+tag;
link_to_array();
int ans=-inf;
L=max(L,l);R=min(R,r);
for (int i=L;i<=R;i++) ans=max(ans,a[i]);
return ans;
}
int qwmin(int L,int R){
if (l>=L&&r<=R) return head->val+tag;
link_to_array();
int ans=inf;
L=max(L,l);R=min(R,r);
for (int i=L;i<=R;i++) ans=min(ans,a[i]);
return ans;
}
pr qnmax(int L,int R){
if (l>=L&&r<=R) return (pr){tail->val+tag,tail->cnt};
link_to_array();
pr ans=(pr){-inf,0};
L=max(L,l);R=min(R,r);
for (int i=L;i<=R;i++) merge_max(ans,(pr){a[i],1});
return ans;
}
pr qnmin(int L,int R){
if (l>=L&&r<=R) return (pr){head->val+tag,head->cnt};
link_to_array();
pr ans=(pr){inf,0};
L=max(L,l);R=min(R,r);
for (int i=L;i<=R;i++) merge_min(ans,(pr){a[i],1});
return ans;
}
}block[1010];
int main()
{
freopen("redbag.in","r",stdin);
freopen("redbag.out","w",stdout);
scanf("%d",&n);
block_size=sqrt(n);
if (block_size<10) block_size=10;
for (int i=1;i<=n;i++) a[i]=read();
for (int i=1;i<=n;i+=block_size) block[++num_block].init(i,i+block_size-1);
scanf("%d",&m);
char str[10]="";int l,r,v;
for (int i=1;i<=m;i++){
scanf("%s",str);l=read();r=read();
if (str[0]=='C'){
v=read();
if (str[1]=='a') for (int i=blo[l];i<=blo[r];i++) block[i].add(l,r,v);else
if (str[1]=='c') for (int i=blo[l];i<=blo[r];i++) block[i].makesame(l,r,v);else
if (str[3]=='a') for (int i=blo[l];i<=blo[r];i++) block[i].cbmax(l,r,v);else
if (str[3]=='i') for (int i=blo[l];i<=blo[r];i++) block[i].cbmin(l,r,v);
}
else{
if (str[1]=='s'){
int ans=0;
for (int i=blo[l];i<=blo[r];i++) ans+=block[i].qsum(l,r);
print(ans);
}else
if (str[1]=='w'&&str[3]=='a'){
int ans=-inf;
for (int i=blo[l];i<=blo[r];i++) ans=max(ans,block[i].qwmax(l,r));
print(ans);
}else
if (str[1]=='w'&&str[3]=='i'){
int ans=inf;
for (int i=blo[l];i<=blo[r];i++) ans=min(ans,block[i].qwmin(l,r));
print(ans);
}else
if (str[1]=='n'&&str[3]=='a'){
pr ans=(pr){-inf,0};
for (int i=blo[l];i<=blo[r];i++) merge_max(ans,block[i].qnmax(l,r));
print(ans.second);
}else
if (str[1]=='n'&&str[3]=='i'){
pr ans=(pr){inf,0};
for (int i=blo[l];i<=blo[r];i++) merge_min(ans,block[i].qnmin(l,r));
print(ans.second);
}
}
}
return 0;
}