【JZOJ 4933】【NOIP2017提高组模拟12.24】C

Description

给出一个正整数序列，要求要兹瓷：(给出l,r)
1. 区间加、减
2. 区间赋值
3. 区间求和
4. 区间求min,max
5. 区间求最长的连续一段相同的数
n,m<105

Solution

裸的线段树一道，恶心死了…

复杂度： O(mlog(n))

Code

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long LL;
const int N=300500;
int read(int &n)
{
    char ch=' ';int q=0,w=1;
for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
if(ch=='-')w=-1,ch=getchar();
for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int n,m;
struct qqww
{
    LL sum,mi,mx,l,r,ls,la,la1,L,R;
}a[N*3],ans;
void doit(int l,int r,int e)
{
if(!a[e].la1)return;
if(a[e].la1==1)
    {
        a[e].sum+=a[e].la*(r-l+1);
        a[e].mx+=a[e].la;
        a[e].mi+=a[e].la;
        a[e].L+=a[e].la;
        a[e].R+=a[e].la;
if(l!=r)
        {
if(!a[e*2].la1)a[e*2].la1=1;
            a[e*2].la+=a[e].la;
if(!a[e*2+1].la1)a[e*2+1].la1=1;
            a[e*2+1].la+=a[e].la;
        }
    }
else 
    {
        a[e].sum=a[e].la*(r-l+1);
        a[e].mi=a[e].mx=a[e].la;
        a[e].L=a[e].R=a[e].la;
        a[e].l=a[e].r=a[e].ls=r-l+1;
if(l!=r)
        {
            a[e*2].la1=2;
            a[e*2].la=a[e].la;
            a[e*2+1].la1=2;
            a[e*2+1].la=a[e].la;
        }
    }
    a[e].la=a[e].la1=0;
}
qqww merge(int l1,int r1,qqww l,qqww r)
{
    qqww ans;
    ans.sum=l.sum+r.sum;
    ans.mx=max(l.mx,r.mx);
    ans.mi=min(l.mi,r.mi);
    ans.l=l.l;ans.r=r.r;
    ans.ls=max(l.ls,r.ls);
if(l.R==r.L)
    {
        ans.ls=max(ans.ls,l.r+r.l);
if(l.l==((l1+r1)/2-l1+1))ans.l+=r.l;
if(r.r==(r1-(l1+r1)/2))ans.r+=l.r;
    }
    ans.L=l.L,ans.R=r.R;
    ans.la=ans.la1=0;
return ans;
}
void change(int l,int r,int e,int l1,int r1,int l2,bool lb)
{
int t=(l+r)>>1;
    doit(l,t,e*2),doit(t+1,r,e*2+1);
if(l==l1&&r==r1)
    {
        a[e].la=l2,a[e].la1=lb+1;
        doit(l,r,e);
return;
    }
if(r1<=t)change(l,t,e*2,l1,r1,l2,lb);
else if(t<l1)change(t+1,r,e*2+1,l1,r1,l2,lb);
else change(l,t,e*2,l1,t,l2,lb),change(t+1,r,e*2+1,t+1,r1,l2,lb);
    a[e]=merge(l,r,a[e*2],a[e*2+1]);
}
qqww find(int l,int r,int e,int l1,int r1)
{
int t=(l+r)>>1;
    doit(l,t,e*2),doit(t+1,r,e*2+1);
if(l==l1&&r==r1)return a[e];
if(r1<=t)return find(l,t,e*2,l1,r1);
else if(t<l1)return find(t+1,r,e*2+1,l1,r1);
else 
            {
return merge(l,r,find(l,t,e*2,l1,t),find(t+1,r,e*2+1,t+1,r1));
            }
}
int main()
{
int q,w,e,E;
read(n),read(m);
    fo(i,1,n)read(q),change(1,n,1,i,i,q,1);
    fo(i,1,m)
    {
read(E),read(q),read(w);
if(E<4)
        {
read(e);
if(E==2)e=-e;
            change(1,n,1,q,w,e,E>2);
        }else
        {
            ans=find(1,n,1,q,w);
if(E==4)printf("%lld\n",ans.sum);
if(E==5)printf("%lld\n",ans.mi);
if(E==6)printf("%lld\n",ans.mx);
if(E==7)printf("%lld\n",ans.ls);
        }
    }
return 0;
}