PKU1177 Picture
参见my blog
hdu3954 level up
#include<iostream>
#include<cstdio>
using namespace std;
const int N=10003;
struct node{
int exp,lev,dis,lazy;
}tr[N<<2];
int T,t,n,k,m,i,need[11],x,y,z;
char s[2];
void pushdown(int t){
if (tr[t].lazy){
tr[t<<1].exp+=tr[t<<1].lev*tr[t].lazy;
tr[t<<1].dis-=tr[t].lazy;
tr[t<<1].lazy+=tr[t].lazy;
tr[t<<1|1].exp+=tr[t<<1|1].lev*tr[t].lazy;
tr[t<<1|1].dis-=tr[t].lazy;
tr[t<<1|1].lazy+=tr[t].lazy;
tr[t].lazy=0;
}
}
void pushup(int t){
tr[t].exp=max(tr[t<<1].exp,tr[t<<1|1].exp);
tr[t].lev=max(tr[t<<1].lev,tr[t<<1|1].lev);
tr[t].dis=min(tr[t<<1].dis,tr[t<<1|1].dis);
}
void add(int t,int l,int r,int x,int y,int v){
if (l==r){
tr[t].exp+=v*tr[t].lev;
while (tr[t].exp>=need[tr[t].lev]) tr[t].lev++;
tr[t].dis=(need[tr[t].lev]-tr[t].exp-1)/tr[t].lev+1;
return;
}
if (x<=l && r<=y){
if (v>=tr[t].dis){
pushdown(t);
int mid=l+r>>1;
add(t<<1,l,mid,x,y,v);
add(t<<1|1,mid+1,r,x,y,v);
pushup(t);
}else{
tr[t].exp+=v*tr[t].lev;
tr[t].dis-=v;
tr[t].lazy+=v;
}
return;
}
pushdown(t);
int mid=l+r>>1;
if (x<=mid) add(t<<1,l,mid,x,y,v);
if (mid<y) add(t<<1|1,mid+1,r,x,y,v);
pushup(t);
}
int query(int t,int l,int r,int x,int y){
if (x<=l && r<=y) return tr[t].exp;
pushdown(t);
int mid=l+r>>1,ans=-1e9;
if (x<=mid) ans=max(ans,query(t<<1,l,mid,x,y));
if (mid<y) ans=max(ans,query(t<<1|1,mid+1,r,x,y));
return ans;
}
int main(){
scanf("%d",&T);
for (t=1;t<=T;t++){
scanf("%d%d%d",&n,&k,&m);
for (i=1;i<k;i++) scanf("%d",&need[i]);
need[k]=1<<30;
for (i=0;i<N<<2;i++) tr[i]=(node){0,1,need[1],0};
printf("Case %d:\n",t);
while (m--){
scanf("%s%d%d",s,&x,&y);
if (s[0]=='W') scanf("%d",&z),add(1,1,n,x,y,z);
else printf("%d\n",query(1,1,n,x,y));
}
putchar('\n');
}
}hdu4027 can you answer these queries?
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=100003;
struct node{
ll v,sum;
}tr[N<<2];
int n,i,q,op,x,y,t;
ll a[N];
void maintain(int t,int l,int r,ll v){
tr[t].v=v;
tr[t].sum=v*(r-l+1);
}
void pushdown(int t,int l,int r){
if (tr[t].v){
int mid=l+r>>1;
maintain(t<<1,l,mid,tr[t].v);
maintain(t<<1|1,mid+1,r,tr[t].v);
tr[t].v=0;
}
}
void pushup(int t){
tr[t].sum=tr[t<<1].sum+tr[t<<1|1].sum;
tr[t].v=tr[t<<1].v==tr[t<<1|1].v?tr[t<<1].v:0;
}
void build(int t,int l,int r){
if (l==r){
tr[t].v=tr[t].sum=a[l];
return;
}
int mid=l+r>>1;
build(t<<1,l,mid);
build(t<<1|1,mid+1,r);
pushup(t);
}
void change(int t,int l,int r,int x,int y){
if (x<=l && r<=y && tr[t].v){
maintain(t,l,r,(ll)sqrt(tr[t].v));
return;
}
pushdown(t,l,r);
int mid=l+r>>1;
if (x<=mid) change(t<<1,l,mid,x,y);
if (mid<y) change(t<<1|1,mid+1,r,x,y);
pushup(t);
}
ll query(int t,int l,int r,int x,int y){
if (x<=l && r<=y) return tr[t].sum;
pushdown(t,l,r);
int mid=l+r>>1;
ll ans=0;
if (x<=mid) ans+=query(t<<1,l,mid,x,y);
if (mid<y) ans+=query(t<<1|1,mid+1,r,x,y);
return ans;
}
int main(){
while (~scanf("%d",&n)){
for (i=1;i<=n;i++) scanf("%lld",&a[i]);
for (i=0;i<N<<2;i++) tr[i].v=tr[i].sum=0;
build(1,1,n);
printf("Case #%d:\n",++t);
scanf("%d",&q);
while (q--){
scanf("%d%d%d",&op,&x,&y);
if (x>y) swap(x,y);
if (!op) change(1,1,n,x,y);
else printf("%lld\n",query(1,1,n,x,y));
}
putchar('\n');
}
}hdu3333 turing tree
#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=30003,M=100003;
struct kk{
int l,r,id;
}b[M];
map<int,int>pre;
ll tr[N],ans[M];
int n,m,i,a[N],T,j;
bool cmp(kk x,kk y){
return x.r<y.r || x.r==y.r && x.l<y.l;
}
void add(int x,int y){
for (;x<=n;x+=x&-x) tr[x]+=y;
}
ll query(int x){
ll s=0;
for (;x;x-=x&-x) s+=tr[x];
return s;
}
int main(){
scanf("%d",&T);
while (T--){
pre.clear();
memset(tr,0,sizeof(tr));
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);
for (i=1;i<=m;i++) scanf("%d%d",&b[i].l,&b[i].r),b[i].id=i;
sort(b+1,b+m+1,cmp);
j=1;
for (i=1;i<=n;i++){
if (pre[a[i]]) add(pre[a[i]],-a[i]);
add(i,a[i]);
for (;j<=m && b[j].r==i;j++) ans[b[j].id]=query(b[j].r)-query(b[j].l-1);
if (j>m) break;
pre[a[i]]=i;
}
for (i=1;i<=m;i++) printf("%lld\n",ans[i]);
}
}hdu3016 man down
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100003;
struct kk{
int h,l,r,val,le,ri;
}a[N];
struct node{
int mark,num;
}tr[N<<2];
int f[N],n,i,le,ri;
bool cmp(kk x,kk y){
return x.h<y.h;
}
int query(int t,int l,int r,int x){
if (l==r) return tr[t].num;
if (tr[t].mark!=-1){
tr[t<<1]=tr[t<<1|1]=tr[t];
return tr[t].num;
}
int mid=l+r>>1;
if (x<=mid) return query(t<<1,l,mid,x);
return query(t<<1|1,mid+1,r,x);
}
void update(int t,int l,int r,int v,int x,int y){
if (x<=l && r<=y){
tr[t].num=v;
tr[t].mark=1;
return;
}
if (tr[t].mark!=-1){
tr[t<<1]=tr[t<<1|1]=tr[t];
tr[t].mark=-1;
}
int mid=l+r>>1;
if (x<=mid) update(t<<1,l,mid,v,x,y);
if (mid<y) update(t<<1|1,mid+1,r,v,x,y);
}
int main(){
while (~scanf("%d",&n)){
n++;a[0].h=0;a[0].l=1;a[0].r=N-1;a[0].val=0;
for (i=1;i<n;i++) scanf("%d%d%d%d",&a[i].h,&a[i].l,&a[i].r,&a[i].val);
sort(a,a+n,cmp);
for (i=0;i<N<<2;i++) tr[i].num=tr[i].mark=-1;
for (i=0;i<n;i++){
a[i].le=query(1,1,N-1,a[i].l);
a[i].ri=query(1,1,N-1,a[i].r);
update(1,1,N-1,i,a[i].l,a[i].r);
}
memset(f,0,sizeof(f));
f[n-1]=100+a[n-1].val;
for (i=n-1;i>=0;i--){
le=a[i].le;
ri=a[i].ri;
f[le]=max(f[le],f[i]+a[le].val);
f[ri]=max(f[ri],f[i]+a[ri].val);
}
printf("%d\n",f[0]?f[0]:-1);
}
}hdu3340 rain in ACStar
#include<cstdio>
#include<algorithm>
using namespace std;
#define C(x) x=lower_bound(h+1,h+n+1,x)-h;
#define M (l+r>>1)
typedef double D;
const int N=100003;
struct node{
D a,b,sum,g;
}tr[N<<2];
struct nn{
int x,y;
}q[N],p[N][7];
int x1,y1,x2,y2,n,i,j,k,t,kk,tt,h[N],T,m,l[N],ii,jj;
D ra,ans;
char c[N];
D cal(D a,int s,D ra){
return a+ra*s;
}
void down(int t,int l,int r){
tr[t<<1].g+=tr[t].g;tr[t<<1|1].g+=tr[t].g;
tr[t<<1].a+=tr[t].a;tr[t<<1|1].b+=tr[t].b;
D Z=cal(tr[t].a,h[M]-h[l],tr[t].g);
tr[t<<1].sum+=1.0*(tr[t].a+Z)*(h[M]-h[l])/2;
tr[t<<1|1].sum+=1.0*(Z+tr[t].b)*(h[r]-h[M])/2;
tr[t<<1].b+=Z;tr[t<<1|1].a+=Z;
tr[t].a=tr[t].b=tr[t].g=0;
}
void update(int t,int l,int r,int x,int y,D a,D b,D ra){
if (x<=l && r<=y){
tr[t].a+=a;tr[t].b+=b;
tr[t].g+=ra;tr[t].sum+=1.0*(a+b)*(h[r]-h[l])/2;
return;
}
down(t,l,r);
if (y<=M) update(t<<1,l,M,x,y,a,b,ra);
else if (x>=M) update(t<<1|1,M,r,x,y,a,b,ra);
else{
D Z=cal(a,h[M]-h[x],ra);
update(t<<1,l,M,x,M,a,Z,ra);
update(t<<1|1,M,r,M,y,Z,b,ra);
}
tr[t].sum=tr[t<<1].sum+tr[t<<1|1].sum;
}
void query(int t,int l,int r,int x,int y){
if (x<=l && r<=y){
ans+=tr[t].sum;
return;
}
down(t,l,r);
if (x<M) query(t<<1,l,M,x,y);
if (M<y) query(t<<1|1,M,r,x,y);
}
int main(){
scanf("%d",&T);
while (T--){
n=k=t=kk=tt=0;
for (i=0;i<N<<2;i++) tr[i].a=tr[i].b=tr[i].g=tr[i].sum=0;
scanf("%d",&m);
for (i=1;i<=m;i++){
do c[i]=getchar();while (c[i]!='Q' && c[i]!='R');
if (c[i]=='Q') k++,scanf("%d%d",&q[k].x,&q[k].y),h[++n]=q[k].x,h[++n]=q[k].y;
else{
t++;
scanf("%d",&l[t]);
for (j=1;j<=l[t];j++) scanf("%d%d",&p[t][j].x,&p[t][j].y),h[++n]=p[t][j].x;
}
}
sort(h+1,h+n+1);
n=unique(h+1,h+n+1)-h-1;
for (i=1;i<=k;i++){
C(q[i].x);C(q[i].y);
}
for (i=1;i<=t;i++)
for (j=1;j<=l[i];j++) C(p[i][j].x);
for (i=1;i<=m;i++)
if (c[i]=='Q') kk++,ans=0,query(1,1,n,q[kk].x,q[kk].y),printf("%.3lf\n",ans);
else for (tt++,j=1;j<=l[tt];j++){
ii=j;jj=j==l[tt]?1:j+1;
x1=p[tt][ii].x;y1=p[tt][ii].y;
x2=p[tt][jj].x;y2=p[tt][jj].y;
if (x1<x2) y1=-y1,y2=-y2;
else swap(x1,x2),swap(y1,y2);
ra=1.0*(y2-y1)/(h[x2]-h[x1]);
update(1,1,n,x1,x2,y1,y2,ra);
}
}
}CF85D Sum of Medians
#include<bits/stdc++.h>
using namespace std;
const int N=100003;
typedef long long ll;
int sum[N<<2],h[N],a[N],fl,i,n,t,pos;
ll ans[N<<2][5];
char s[N][5];
void update(int t,int l,int r,int x){
sum[t]+=fl*2-1;
if (l==r){
ans[t][0]=fl*h[l];
return;
}
int m=l+r>>1;
if (x<=m) update(t<<1,l,m,x);
else update(t<<1|1,m+1,r,x);
for (int i=0;i<5;i++) ans[t][i]=ans[t<<1][i]+ans[t<<1|1][(i-sum[t<<1]%5+5)%5];
}
int main(){
while (~scanf("%d",&n)){
for (i=0;i<n;i++){
scanf("%s",s[i]);
if (s[i][0]!='s') scanf("%d",&a[i]),h[t++]=a[i];
}
memset(sum,0,sizeof(sum));
memset(ans,0,sizeof(ans));
sort(h,h+t);
t=unique(h,h+t)-h;
for (i=0;i<n;i++)
if (s[i][0]=='s') printf("%lld\n",ans[1][2]);
else{
fl=(s[i][0]=='a');
pos=lower_bound(h,h+t,a[i])-h;
update(1,1,n,pos);
}
}
}spojGSS2 Can you answer these queries ||
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100003;
struct node{
int old,oldcov,now,nowcov;
}tr[N<<2];
struct kk{
int x,y,id;
}q[N];
int n,m,i,ans[N],pos[N<<1],a[N],j;
bool cmp(kk x,kk y){
return x.y<y.y;
}
void down(int t){
tr[t<<1].oldcov=max(tr[t<<1].oldcov,tr[t<<1].nowcov+tr[t].oldcov);
tr[t<<1|1].oldcov=max(tr[t<<1|1].oldcov,tr[t<<1|1].nowcov+tr[t].oldcov);
tr[t<<1].old=max(tr[t<<1].old,tr[t<<1].now+tr[t].oldcov);
tr[t<<1|1].old=max(tr[t<<1|1].old,tr[t<<1|1].now+tr[t].oldcov);
tr[t<<1].nowcov+=tr[t].nowcov;
tr[t<<1|1].nowcov+=tr[t].nowcov;
tr[t<<1].now+=tr[t].nowcov;
tr[t<<1|1].now+=tr[t].nowcov;
tr[t].nowcov=tr[t].oldcov=0;
}
void update(int t,int l,int r,int x,int y,int v){
if (x<=l && r<=y){
tr[t].oldcov=max(tr[t].oldcov,tr[t].nowcov+=v);
tr[t].old=max(tr[t].old,tr[t].now+=v);
return;
}
down(t);
int mid=l+r>>1;
if (x<=mid) update(t<<1,l,mid,x,y,v);
if (mid<y) update(t<<1|1,mid+1,r,x,y,v);
tr[t].now=max(tr[t<<1].now,tr[t<<1|1].now);
tr[t].old=max(tr[t<<1].old,tr[t<<1|1].old);
}
int query(int t,int l,int r,int x,int y){
if (x<=l && r<=y) return tr[t].old;
down(t);
int mid=l+r>>1,ans=-1e9;
if (x<=mid) ans=max(ans,query(t<<1,l,mid,x,y));
if (mid<y) ans=max(ans,query(t<<1|1,mid+1,r,x,y));
return ans;
}
int main(){
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);
for (i=0;i<m;i++) scanf("%d%d",&q[i].x,&q[i].y),q[i].id=i;
sort(q,q+m,cmp);
for (i=1;i<=n;i++){
update(1,1,n,pos[a[i]+N]+1,i,a[i]);
pos[a[i]+N]=i;
for (;j<m && q[j].y==i;j++) ans[q[j].id]=query(1,1,n,q[j].x,q[j].y);
if (j>=m) break;
}
for (i=0;i<m;i++) printf("%d\n",ans[i]);
}
京公网安备 11010502036488号