segment tree beats 练习题

posted on 2019-04-18 15:33:57 | under 未分类 |

#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;typedef long long ll;
const ll inf=(1LL<<60);const ll low_inf=(1LL<<50);
int n;int m;ll cur;//int TOT;
struct linetree
{
struct data
{
ll val;int fr;
friend bool operator <(data a,data b){return a.val<b.val;}
void operator +=(ll del){val+=del;}
}mi[N<<2];ll nmi[N<<2];
{
}
inline void appmx(int p,ll lim)
{
mi[p].val=max(lim,mi[p].val);
nmi[p]=max(nmi[p],lim);to_mi[p]=max(to_mi[p],lim);
}
inline void ins(int p,ll val)
{
//  if(val!=0&&val<low_inf)printf("ins  %lld %lld %lld\n",val,mi[p].val,nmi[p]);
if(mi[p].val>=val)
{
if(mi[p].val!=val)nmi[p]=mi[p].val;
mi[p].val=val;
}
else if(nmi[p]>=val)nmi[p]=val;
}
inline void ud(int p,int p1,int p2)
{
mi[p].val=mi[p1].val;nmi[p]=nmi[p1];

//  ll qu[4]={mi[p1].val,nmi[p1],mi[p2].val,nmi[p2]
//  mi[p].val=qu[0];nmi[p]=qu[1];
ins(p,mi[p2].val);ins(p,nmi[p2]);
//  if(nmi[p]<low_inf)printf("mi=%lld,nmi=%lld\n",mi[p].val,nmi[p]);
if(mi[p].val==mi[p1].val&&mi[p].val==mi[p2].val)
mi[p].fr=2;
else if(mi[p].val==mi[p1].val)mi[p].fr=0;
else mi[p].fr=1;
}
inline void pd(int p,int p1,int p2)
{
if(splb[p])
{
switch(mi[p].fr)
{
case 0:{splb[p1]+=splb[p];break;}
case 1:{splb[p2]+=splb[p];break;}
case 2:{splb[p1]+=splb[p];splb[p2]+=splb[p];break;}
}splb[p]=0;
}
if(to_mi[p]>-low_inf)
appmx(p1,to_mi[p]),appmx(p2,to_mi[p]),to_mi[p]=-inf;
}
inline void stadd(int p,int l,int r,int dl,int dr,ll del)
{
int mid=(l+r)>>1;pd(p,p<<1,p<<1|1);
ud(p,p<<1,p<<1|1);
}
inline void stmx(int p,int l,int r,int dl,int dr,ll lim)
{
if(l==dl&&dr==r)
{

//  if(nmi[p]==54421679)printf("%d %d,mi=%lld,nmi=%lld,lim=%lld\n",l,r,mi[p].val,nmi[p],lim);
if(lim<=mi[p].val)return;

if(lim<nmi[p]){splb[p]++;appmx(p,lim);return;}
//printf("mi=%lld,nmi=%lld,lim=%lld\n",mi[p].val,nmi[p],lim);
//TOT++;
}
int mid=(l+r)>>1;pd(p,p<<1,p<<1|1);
if(dl<mid)stmx(p<<1,l,mid,dl,min(dr,mid),lim);
if(mid<dr)stmx(p<<1|1,mid,r,max(dl,mid),dr,lim);
ud(p,p<<1,p<<1|1);
}
inline int qry(int p,int l,int r,int pos)
{
if(r-l==1)
{
//  printf("%lld ",mi[p].val);
cur=mi[p].val;
return v[p]+splb[p];
}
int mid=(l+r)>>1;pd(p,p<<1,p<<1|1);
if(pos<=mid)return v[p]+qry(p<<1,l,mid,pos);
else return v[p]+qry(p<<1|1,mid,r,pos);
}
inline void build(int p,int l,int r,ll* a)
{
to_mi[p]=-inf;
if(r-l==1)
{
mi[p].val=a[r];nmi[p]=low_inf;return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid,a);build(p<<1|1,mid,r,a);
ud(p,p<<1,p<<1|1);
}
}lt;
ll a[N];char mde[N];
ll ans1[N];int ans2[N];int CNT;
int main()
{
//freopen("tst","r",stdin);freopen("my","w",stdout);
//  freopen("seq3.out","r",stdin);
//  ++CNT;
//  while(scanf("%lld%d",&ans1[CNT],&ans2[CNT])!=-1)++CNT;
//  fclose(stdin);CNT=1;
//  freopen("seq3.in","r",stdin);
//freopen("mtst.txt","w",stdout);
freopen("seq.in","r",stdin);freopen("seq.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
lt.build(1,0,n,a);
scanf("%d",&m);
for(int i=1,l,r,del;i<=m;i++)
{
//if(i%1000==0)printf("i=%d,ratio=%.3lf\n",i,(double)TOT/i);
scanf("%s",mde+1);
switch(mde[1])
{
case 'A':
{
scanf("%d%d%d",&l,&r,&del);
break;
}
case 'M':
{
scanf("%d%d%d",&l,&r,&del);
lt.stmx(1,0,n,l-1,r,del);
//  if(i>=5700)printf("stmx %d %d %d\n",l,r,del);
break;
}
case 'Q':
{
scanf("%d",&l);
int cur2=lt.qry(1,0,n,l);
printf("%lld %d\n",cur,cur2);
//  if(cur!=ans1[CNT]||cur2!=ans2[CNT])
//  {
//      printf("%lld %d %lld %d\n",cur,cur2,ans1[CNT],ans2[CNT]);
////
//  return 0;}//int k;while(1)k++;}
//  ++CNT;
break;
}

}
//  if(i>=5700)
//  {
//      int cur2=lt.qry(1,0,n,7216);
//      printf("%lld %d\n",cur,cur2);
//  }
}
return 0;
}