区间

区间

关注
发信
关注(28)粉丝(399)

线段树模板+习题

线段树自用模板

#include <iostream>
using namespace std;
const int MAX_N=10010;
int s[MAX_N<<2];
void up(int p)
{
    s[p]=s[p<<1]+s[p<<1|1];
}
void modify(int p,int l,int r,int x,int v)
{//p l r为当前更新到的结点、左右端点，对第x个元素加上v 
    if(l==r)
    {
        s[p]+=v;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)modify(p<<1,l,mid,x,v);
    else modify(p<<1|1,mid+1,r,x,v);
    up(p);
}
int query(int p,int l,int r,int x,int y)
{//p l r为当前更新到的结点、左右端点，x y为查询区间范围 
    if(x<=l&&r<=y)
    {
        return s[p];
    }
    int mid=(l+r)>>1,res=0;
    if(x<=mid)res+=query(p<<1,l,mid,x,y);
    if(y>mid) res+=query(p<<1|1,mid+1,r,x,y);
    return res;
}


int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int d;cin>>d;
        modify(1,1,n,i,d);
    }
    int q;
    cin>>q;
    while(q--)
    {
        int d,x,y;
        cin>>d>>x>>y;
        if(d==0)modify(1,1,n,x,y);
        else cout<<query(1,1,n,x,y)<<endl;
    }
    return 0;
}
View Code

线段树+lazy标记自用模板

modify是指区间[x,y]中都加c，如果是数值更改而不是累加，把modify和down里的+=改成=。

#include <iostream>
using namespace std;
const int MAX_N=10010;
int s[MAX_N<<2],col[MAX_N<<2];
void up(int p)
{
    s[p]=s[p<<1]+s[p<<1|1];
}
void down(int p,int l,int r)
{
    if(col[p])
    {
        int mid=(l+r)>>1;
        s[p<<1]+=col[p]*(mid-l+1);
        s[p<<1|1]+=col[p]*(r-mid);
        col[p<<1]+=col[p];
        col[p<<1|1]+=col[p];
        col[p]=0;
    }
}
void modify(int p,int l,int r,int x,int y,int c)
{
    if(x<=l&&r<=y)
    {
        s[p]+=(r-l+1)*c;
        col[p]+=c;
        return;
    }
    down(p,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)modify(p<<1,l,mid,x,y,c);
    if(y>mid)modify(p<<1|1,mid+1,r,x,y,c);
    up(p);
}
int query(int p,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        return s[p];
    }
    down(p,l,r);
    int mid=(l+r)>>1,res=0;
    if(x<=mid)res+=query(p<<1,l,mid,x,y);
    if(y>mid)res+=query(p<<1|1,mid+1,r,x,y);
    return res;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int d;cin>>d;
        modify(1,1,n,i,i,d);
    }
    int q;
    cin>>q;
    while(q--)
    {
        int d,x,y,c;
        cin>>d>>x>>y;
        if(d==0)cin>>c,modify(1,1,n,x,y,c);
        else cout<<query(1,1,n,x,y)<<endl;
    }
    return 0;
}
View Code

01串的区间翻转，询问区间内最长的连续1串

思路:维护区间内的最大值和区间两端的结果，将0和1分别保存。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m,op,x,y;
int a[maxn];
int s[maxn<<2][2],cl[maxn<<2][2],cr[maxn<<2][2];
int col[maxn<<2],len[maxn<<2];

void up(int p)
{
    for(int i=0;i<2;i++)
    {
        s[p][i]=cr[p<<1][i]+cl[p<<1|1][i];
        s[p][i]=max(s[p<<1][i],s[p][i]);
        s[p][i]=max(s[p<<1|1][i],s[p][i]);
        cl[p][i]=cl[p<<1][i];if(cl[p<<1][i]==len[p<<1])cl[p][i]+=cl[p<<1|1][i];
        cr[p][i]=cr[p<<1|1][i];if(cr[p<<1|1][i]==len[p<<1|1])cr[p][i]+=cr[p<<1][i];
    }
}
void down(int p)
{
    if(col[p])
    {
        swap(s[p<<1][0],s[p<<1][1]);
        swap(s[p<<1|1][0],s[p<<1|1][1]);
        swap(cl[p<<1][0],cl[p<<1][1]);
        swap(cl[p<<1|1][0],cl[p<<1|1][1]);
        swap(cr[p<<1][0],cr[p<<1][1]);
        swap(cr[p<<1|1][0],cr[p<<1|1][1]);
        col[p<<1]^=1;
        col[p<<1|1]^=1;
        col[p]=0;
    }
}
void build(int p,int l,int r)
{
    col[p]=0;len[p]=r-l+1;
    if(l==r)
    {
        int v=a[l];
        s[p][v]=cl[p][v]=cr[p][v]=1;
        v^=1;
        s[p][v]=cl[p][v]=cr[p][v]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    up(p);
}
void modify(int p,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        swap(s[p][0],s[p][1]);
        swap(cl[p][0],cl[p][1]);
        swap(cr[p][0],cr[p][1]);
        col[p]^=1;
        return;
    }
    down(p);
    int mid=(l+r)>>1;
    if(x<=mid)modify(p<<1,l,mid,x,y);
    if(y>mid)modify(p<<1|1,mid+1,r,x,y);
    up(p);
}

struct atom
{
    int sum,left,right;
    bool full;
};
atom operator +(atom a,atom b)
{
    atom res;
    res.sum=a.right+b.left;
    res.sum=max(a.sum,res.sum);
    res.sum=max(b.sum,res.sum);
    res.left=a.left;if(a.full)res.left+=b.left;
    res.right=b.right;if(b.full)res.right+=a.right;
    res.full=a.full&&b.full;
    return res;
}
atom query(int p,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    return (atom){s[p][1],cl[p][1],cr[p][1],s[p][1]==len[p]};
    down(p);
    int mid=(l+r)>>1;
    if(y<=mid)return query(p<<1,l,mid,x,y);
    else if(x>mid)return query(p<<1|1,mid+1,r,x,y);
    else return query(p<<1,l,mid,x,y)+query(p<<1|1,mid+1,r,x,y);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    build(1,1,n);
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(op==0)
        {
            atom ans=query(1,1,n,x,y);
            printf("%d\n",ans.sum);
        }
        else
        {
            modify(1,1,n,x,y);
        }
    }
    return 0;
}
View Code

洛谷线段树模板2，又忘记取模了5555555

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=1e5+7;
ll mod;
ll a[maxn];
ll s[maxn<<2],col1[maxn<<2],col2[maxn<<2];//col1是乘，col2是加 

void up(ll p)
{
    s[p]=s[p<<1]+s[p<<1|1];
    s[p]%=mod;
}

void build(ll p,ll l,ll r)
{
    col1[p]=1;
    col2[p]=0;
    if(l==r)
    {
        s[p]=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    up(p);
}
void down(ll p,ll l,ll r)
{
    if(col1[p]!=1)
    {
        s[p<<1]*=col1[p];s[p<<1]%=mod;
        s[p<<1|1]*=col1[p];s[p<<1|1]%=mod;
        col1[p<<1]*=col1[p];col1[p<<1]%=mod;
        col1[p<<1|1]*=col1[p];col1[p<<1|1]%=mod;
        col2[p<<1]*=col1[p];col2[p<<1]%=mod;
        col2[p<<1|1]*=col1[p];col2[p<<1|1]%=mod;
        col1[p]=1;
    }
    if(col2[p])
    {
        ll mid=(l+r)>>1;
        s[p<<1]+=col2[p]*(mid-l+1);s[p<<1]%=mod;
        s[p<<1|1]+=col2[p]*(r-mid);s[p<<1|1]%=mod;
        col2[p<<1]+=col2[p];col2[p<<1]%=mod;
        col2[p<<1|1]+=col2[p];col2[p<<1|1]%=mod;
        col2[p]=0;
    }

}

void modify1(ll p,ll l,ll r,ll x,ll y,ll c)//乘 
{
    if(x<=l&&r<=y)
    {
        s[p]*=c;
        s[p]%=mod;
        col1[p]*=c;col1[p]%=mod;
        col2[p]*=c;col2[p]%=mod;
        return;
    }
    down(p,l,r);
    ll mid=(l+r)>>1;
    if(x<=mid)modify1(p<<1,l,mid,x,y,c);
    if(y>mid)modify1(p<<1|1,mid+1,r,x,y,c);
    up(p);
}

void modify2(ll p,ll l,ll r,ll x,ll y,ll c)//加 
{
    if(x<=l&&r<=y)
    {
        s[p]+=(r-l+1)*c;
        s[p]%=mod;
        col2[p]+=c;col2[p]%=mod;
        return;
    }
    down(p,l,r);
    ll mid=(l+r)>>1;
    if(x<=mid)modify2(p<<1,l,mid,x,y,c);
    if(y>mid)modify2(p<<1|1,mid+1,r,x,y,c);
    up(p);
}

ll query(ll p,ll l,ll r,ll x,ll y)
{
    if(x<=l&&r<=y)
    {
        return s[p]%mod;
    }
    down(p,l,r);
    ll mid=(l+r)>>1,res=0;
    if(x<=mid)res+=query(p<<1,l,mid,x,y);
    if(y>mid)res+=query(p<<1|1,mid+1,r,x,y);
    return res%mod;
}

int main()
{
    ll n,m;
    scanf("%lld%lld%lld",&n,&m,&mod);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    while(m--)
    {
        ll op,x,y,k;
        scanf("%lld%lld%lld",&op,&x,&y);
        if(op==1)
        {
            scanf("%lld",&k);
            modify1(1,1,n,x,y,k);
        }
        else if(op==2)
        {
            scanf("%lld",&k);
            modify2(1,1,n,x,y,k);
        }
        else
        {
            int ans=query(1,1,n,x,y);
            cout<<ans<<endl;
        }
    }
    return 0;

}
View Code

poj3264求区间min、max之差

#include<iostream>
#include<stdio.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn=5e4+10;
int s[maxn<<2],s2[maxn<<2],col[maxn<<2],col2[maxn<<2];
void up(int p)
{
    s[p]=max(s[p<<1],s[p<<1|1]);
    s2[p]=min(s2[p<<1],s2[p<<1|1]);
}
void down(int p,int l,int r)
{
    if(col[p])
    {
        s[p<<1]=max(s[p<<1],col[p]);
        s[p<<1|1]=max(s[p<<1|1],col[p]);
        col[p<<1]=col[p<<1|1]=col[p];
        col[p]=0;
    }
    if(col2[p])
    {
        s2[p<<1]=min(s2[p<<1],col2[p]);
        s2[p<<1|1]=min(s2[p<<1|1],col2[p]);
        col2[p<<1]=col2[p<<1|1]=col2[p];
        col2[p]=0;
    }
}
void modify(int p,int l,int r,int x,int y,int c)
{
    if(x<=l&&r<=y)
    {
        s[p]=c;
        s2[p]=c;
        col[p]=c;
        col2[p]=c;
        return;
    }
    down(p,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)modify(p<<1,l,mid,x,y,c);
    if(y>mid)modify(p<<1|1,mid+1,r,x,y,c);
    up(p);
}
int query1(int p,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        return s[p];
    }
    down(p,l,r);
    int mid=(l+r)>>1,res=0;
    if(x<=mid)res=max(res,query1(p<<1,l,mid,x,y));
    if(y>mid)res=max(res,query1(p<<1|1,mid+1,r,x,y));
    return res;
}
int query2(int p,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        return s2[p];
    }
    down(p,l,r);
    int mid=(l+r)>>1,res=inf;
    if(x<=mid)res=min(res,query2(p<<1,l,mid,x,y));
    if(y>mid)res=min(res,query2(p<<1|1,mid+1,r,x,y));
    return res;
}



int main()
{
    int n,q,a[maxn]={0};
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        modify(1,1,n,i,i,a[i]);
    }
    for(int i=1;i<=q;i++)
    {
        int l,r,ans;
        scanf("%d%d",&l,&r);
        ans=query1(1,1,n,l,r)-query2(1,1,n,l,r);
        printf("%d\n",ans);
    }
    return 0;
}
View Code

 hdu4027modify为根号，四舍五入约等于暴力，开long long，x不一定小于y

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
long long s[maxn<<2],col[maxn<<2];
void up(int p)
{
    s[p]=s[p<<1]+s[p<<1|1];
}
void down(int p,int l,int r)
{
    if(col[p])
    {
        int mid=(l+r)>>1;
        s[p<<1]+=col[p]*(mid-l+1);
        s[p<<1|1]+=col[p]*(r-mid);
        col[p<<1]+=col[p];
        col[p<<1|1]+=col[p];
        col[p]=0;
    }
}

void build(int p,int l,int r)
{
    if(l==r)
    {
        scanf("%lld",&s[p]);
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    up(p);
}

void modify(int p,int l,int r,int x,int y)
{
    if(l==r)
    {
        s[p]=sqrt(s[p]);
        return;
    }
    if(x<=l&&r<=y&&s[p]==r-l+1)return;
    int mid=(l+r)>>1;
    if(x<=mid)modify(p<<1,l,mid,x,y);
    if(y>mid)modify(p<<1|1,mid+1,r,x,y);
    up(p);
}

long long query(int p,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)return s[p];
    down(p,l,r);
    int mid=(l+r)>>1;
    long long res=0;
    if(x<=mid)res+=query(p<<1,l,mid,x,y);
    if(y>mid)res+=query(p<<1|1,mid+1,r,x,y);
    return res;
}


int main()
{
    int n,t=1;
    while(scanf("%d",&n)!=EOF)
    {
        memset(s,0,sizeof s);
        memset(col,0,sizeof col);
        printf("Case #%d:\n",t++);
        build(1,1,n);
        int m;
        scanf("%d",&m);
        while(m--)
        {
            int op,x,y;
            scanf("%d%d%d",&op,&x,&y);
            if(op==0)
            {
                if(x>y)swap(x,y);
                modify(1,1,n,x,y);
            }
            else
            {
                if(x>y)swap(x,y);
                long long ans=query(1,1,n,x,y);
                printf("%lld\n",ans);
            }
        }
        printf("\n");
    }
    return 0;
}
View Code

hdu4578，+c,*c,=c操作，查询区间和、区间平方和、区间立方和

https://blog.csdn.net/weixin_44077863/article/details/100523007

初始化，lazy=1(乘法标记)，lazy=lazy=0

sum1=x+x+...+x

sum2=x+x+...+x

sum3=x+x+...+x

①+c

sum=sum+n×c

sum=sum+2c×sum+nc

sum=sum+3c×sum+3csum+nc

lazy+=c

②×c

sum=c×sum

sum=c×sum

sum=c×sum

lazy×=c，lazy×=c

③=c

sum=c×n

sum=c×n

sum=c×n

lazy=0，lazy=1，lazy=c

④查询sum,sum或者sum

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int mod=10007;
int s1[maxn<<2],s2[maxn<<2],s3[maxn<<3],col1[maxn<<2],col2[maxn<<2],col3[maxn<<2];
void build(int p,int l,int r)
{
    s1[p]=s2[p]=s3[p]=col1[p]=col3[p]=0;
    col2[p]=1;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}

void up(int p)
{
    s1[p]=(s1[p<<1]+s1[p<<1|1])%mod;
    s2[p]=(s2[p<<1]+s2[p<<1|1])%mod;
    s3[p]=(s3[p<<1]+s3[p<<1|1])%mod;
}
void down(int p,int l,int r)
{
    int mid=(l+r)>>1;
    int nl=mid-l+1,nr=r-mid;
    if(col3[p])
    {
        s1[p<<1]=col3[p]*nl%mod;
        s1[p<<1|1]=col3[p]*nr%mod;
        s2[p<<1]=(col3[p]*col3[p]%mod)*nl%mod;
        s2[p<<1|1]=(col3[p]*col3[p]%mod)*nr%mod;
        s3[p<<1]=(col3[p]*col3[p]%mod)*(col3[p]*nl%mod)%mod;
        s3[p<<1|1]=(col3[p]*col3[p]%mod)*(col3[p]*nr%mod)%mod;
        col1[p<<1]=col1[p<<1|1]=0;
        col2[p<<1]=col2[p<<1|1]=1;
        col3[p<<1]=col3[p<<1|1]=col3[p];
    }
    if(col2[p]>1)
    {
        s1[p<<1]=s1[p<<1]*col2[p]%mod;
        s1[p<<1|1]=s1[p<<1|1]*col2[p]%mod;
        s2[p<<1]=(s2[p<<1]*col2[p]%mod)*col2[p]%mod;
        s2[p<<1|1]=(s2[p<<1|1]*col2[p]%mod)*col2[p]%mod;
        s3[p<<1]=(s3[p<<1]*col2[p]%mod)*(col2[p]*col2[p]%mod)%mod;
        s3[p<<1|1]=(s3[p<<1|1]*col2[p]%mod)*(col2[p]*col2[p]%mod)%mod;
        col1[p<<1]=col1[p<<1]*col2[p]%mod;
        col1[p<<1|1]=col1[p<<1|1]*col2[p]%mod;
        col2[p<<1]=col2[p<<1]*col2[p]%mod;
        col2[p<<1|1]=col2[p<<1|1]*col2[p]%mod;
    }
    if(col1[p])
    {
        s3[p<<1]=(s3[p<<1]+(3*col1[p]%mod)*s2[p<<1]%mod+(3*col1[p]%mod)*(col1[p]*s1[p<<1]%mod)%mod+(nl*col1[p]%mod)*(col1[p]*col1[p]%mod)%mod)%mod;
        s3[p<<1|1]=(s3[p<<1|1]+(3*col1[p]%mod)*s2[p<<1|1]%mod+(3*col1[p]%mod)*(col1[p]*s1[p<<1|1]%mod)%mod+(nr*col1[p]%mod)*(col1[p]*col1[p]%mod)%mod)%mod;
        s2[p<<1]=(s2[p<<1]+(2*col1[p]%mod)*s1[p<<1]%mod+(nl*col1[p]%mod)*col1[p]%mod)%mod;
        s2[p<<1|1]=(s2[p<<1|1]+(2*col1[p]%mod)*s1[p<<1|1]%mod+(nr*col1[p]%mod)*col1[p]%mod)%mod;
        s1[p<<1]=(s1[p<<1]+nl*col1[p]%mod)%mod;
        s1[p<<1|1]=(s1[p<<1|1]+nr*col1[p]%mod)%mod;
        col1[p<<1]=(col1[p<<1]+col1[p])%mod;
        col1[p<<1|1]=(col1[p<<1|1]+col1[p])%mod;
    }
    col1[p]=0;col2[p]=1;col3[p]=0;
}

void modify(int p,int l,int r,int x,int y,int c,int op)
{
    if(x<=l&&r<=y)
    {
        int &t1=s1[p],&t2=s2[p],&t3=s3[p],len=r-l+1;
        if(op==1)
        {
            t3=(t3+(3*c%mod)*t2%mod+(3*c%mod)*(c*t1%mod)%mod+(len*c%mod)*(c*c%mod)%mod)%mod;
            t2=(t2+(2*c%mod)*t1%mod+(len*c%mod)*c%mod)%mod;
            t1=(t1+len*c%mod)%mod;
            col1[p]=(col1[p]+c)%mod;
        }
        if(op==2)
        {
            t3=(t3*c%mod)*(c*c%mod)%mod;
            t2=(t2*c%mod)*c%mod;
            t1=t1*c%mod;
            col2[p]=col2[p]*c%mod;
            col1[p]=col1[p]*c%mod;
        }
        if(op==3)
        {
            t3=(len*c%mod)*(c*c%mod)%mod;
            t2=(len*c%mod)*c%mod;
            t1=len*c%mod;
            col3[p]=c;col2[p]=1;col1[p]=0;
        }
        return;
    }
    down(p,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)modify(p<<1,l,mid,x,y,c,op);
    if(y>mid)modify(p<<1|1,mid+1,r,x,y,c,op);
    up(p);
}

int query(int p,int l,int r,int x,int y,int op)
{
    if(x<=l&&r<=y)
    {
        if(op==1)return s1[p];
        if(op==2)return s2[p];
        if(op==3)return s3[p];
    }
    down(p,l,r);
    int mid=(l+r)>>1,res=0;
    if(x<=mid)res=(res+query(p<<1,l,mid,x,y,op))%mod;
    if(y>mid)res=(res+query(p<<1|1,mid+1,r,x,y,op))%mod;
    return res%mod;
}


int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0)return 0;
        build(1,1,n);
        for(int i=0;i<m;i++)
        {
            int op,x,y,c;
            scanf("%d%d%d%d",&op,&x,&y,&c);
            if(op!=4)
            {
                modify(1,1,n,x,y,c,op);
            }
            else
            {
                int ans=query(1,1,n,x,y,c);
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}
View Code

 hdu4614，放花或者清理花，线段树+二分，col注意设为-1

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
int s[maxn<<2],col[maxn<<2],n,q;
void up(int p)
{
    s[p]=s[p<<1]+s[p<<1|1];
}
void build(int p,int l,int r)
{
    col[p]=-1;
    s[p]=r-l+1;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
void down(int p,int l,int r)
{
    if(col[p]!=-1)
    {
        int mid=(l+r)>>1;
        s[p<<1]=col[p]*(mid-l+1);
        s[p<<1|1]=col[p]*(r-mid);
        col[p<<1]=col[p<<1|1]=col[p];
        col[p]=-1;
    }
}
void modify(int p,int l,int r,int x,int y,int c)
{
    if(x<=l&&r<=y)
    {
        s[p]=(r-l+1)*c;
        col[p]=c;
        return;
    }
    down(p,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)modify(p<<1,l,mid,x,y,c);
    if(y>mid)modify(p<<1|1,mid+1,r,x,y,c);
    up(p);
}
int query(int p,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        return s[p];
    }
    down(p,l,r);
    int mid=(l+r)>>1,res=0;
    if(x<=mid)res+=query(p<<1,l,mid,x,y);
    if(y>mid)res+=query(p<<1|1,mid+1,r,x,y);
    return res;
}

int binsort(int x,int num)
{
    int low=x,high=n,mid,ans=0;
    while(low<=high)
    {
        mid=(low+high)>>1;
        if(query(1,1,n,x,mid)>=num)
        {
            high=mid-1;
            ans=mid;
        }
        else
        {
            low=mid+1;
        }
    }
    return ans;
}



int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&q);
        build(1,1,n);
        while(q--)
        {
            int op,x,y;
            scanf("%d%d%d",&op,&x,&y);
            x++;
            if(op==1)
            {
                int cnt=min(query(1,1,n,x,n),y);
                if(cnt==0)printf("Can not put any one.\n");
                else
                {
                    int ans1=binsort(x,1),ans2=binsort(x,cnt);
                    printf("%d %d\n",ans1-1,ans2-1);
                    modify(1,1,n,ans1,ans2,0);
                }
            }
            else
            {
                y++;
                int ans=query(1,1,n,x,y);
                printf("%d\n",y-x+1-ans);
                modify(1,1,n,x,y,1);
            }
        }
        printf("\n");
    }
    return 0;
}
View Code

 hdu1540，区间合并

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+10;
int n,m;
struct node
{
    int l,r,cnt,len;
}s[maxn<<2];

void up(int p,int l,int r)
{
    s[p].l=s[p<<1].l;
    if(s[p<<1].l==s[p<<1].len)s[p].l+=s[p<<1|1].l;
    s[p].r=s[p<<1|1].r;
    if(s[p<<1|1].r==s[p<<1|1].len)s[p].r+=s[p<<1].r;
    s[p].cnt=max(max(s[p<<1].cnt,s[p<<1|1].cnt),s[p<<1].r+s[p<<1|1].l);
}


void build(int p,int l,int r)
{
    s[p].l=s[p].r=s[p].cnt=s[p].len=r-l+1;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}

void modify(int p,int l,int r,int x,int c)
{
    if(l==r)
    {
        s[p].l=s[p].r=s[p].cnt=c;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)modify(p<<1,l,mid,x,c);
    else modify(p<<1|1,mid+1,r,x,c);
    up(p,l,r);
}




int query(int p,int l,int r,int x)
{
    if(l==r||s[p].cnt==s[p].len||!s[p].cnt)return s[p].cnt;
    int mid=(l+r)>>1;
    if(x<=mid-s[p<<1].r)return query(p<<1,l,mid,x);
    if(x>mid+s[p<<1|1].l)return query(p<<1|1,mid+1,r,x);
    return s[p<<1].r+s[p<<1|1].l;
}


int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        stack<int> st;
        build(1,1,n);
        while(m--)
        {
            char ch;
            int num;
            cin>>ch;
            if(ch=='D')
            {
                cin>>num;
                st.push(num);
                modify(1,1,n,num,0);
            }
            else if(ch=='Q')
            {
                cin>>num;
                int res=query(1,1,n,num);
                cout<<res<<endl;
            }
            else
            {
                int tmp=st.top();st.pop();
                modify(1,1,n,tmp,1);
            }
        }
    }
    return 0;
}
View Code

 hdu3974

https://blog.csdn.net/weixin_44077863/article/details/100050457

①找到根节点dfs建多叉树，tree[p].l表示p节点的编号，它的儿子节点的编号从tree[p].l+1开始计数，一直到某个数cnt，这个树就是tree[p].r，所以l和r表示了该节点的范围

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int l,r,job,lazy;
    vector<int> son;
}tree[50005];

bool notroot[50005];
int cnt=0;
void dfsbuild(int p)
{
    tree[p].job=tree[p].lazy=-1;
    tree[p].l=++cnt;
    for(auto x:tree[p].son)dfsbuild(x);
    tree[p].r=cnt;
}
void down(int p)
{
    if(tree[p].lazy==-1)return;
    for(auto s:tree[p].son)tree[s].job=tree[s].lazy=tree[p].lazy;
    tree[p].lazy=-1;
}

void update(int p,int x,int y)
{
    if(p==x)
    {
        tree[p].job=tree[p].lazy=y;
        return;
    }
    down(p);
    for(auto s:tree[p].son)
    {
        if(tree[s].l<=tree[x].l&&tree[x].l<=tree[s].r)
        update(s,x,y);
    }
}
int query(int p,int x)
{
    if(x==p)return tree[p].job;
    down(p);
    for(auto s:tree[p].son)
    {
        if(tree[s].l<=tree[x].l&&tree[x].l<=tree[s].r)
            return query(s,x);
    }
}

int main()
{
    int T,t=1;
    scanf("%d",&T);
    while(T--)
    {
        int n,u,v,m,root;
        cnt=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)tree[i].son.clear(),notroot[i]=0;
        for(int i=1;i<n;i++)scanf("%d%d",&u,&v),tree[v].son.push_back(u),notroot[u]=1;
        for(int i=1;i<=n;i++)if(!notroot[i])root=i;
        dfsbuild(root);
        scanf("%d",&m);
        printf("Case #%d:\n",t++);
        while(m--)
        {
            char op;
            int x,y;
            cin>>op>>x;
            if(op=='C')printf("%d\n",query(root,x));
            else scanf("%d",&y),update(root,x,y);
        }
    }
    return 0;
}
View Code

 ②用线段树来进行区间染色，用dfs来建区间

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+10;
int tree[maxn<<2],lid[maxn],rid[maxn],cnt=0;
vector<int> son[maxn];
bool notroot[maxn];

void build(int p,int l,int r)
{
    tree[p]=-1;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}

void dfs(int p)
{
    lid[p]=++cnt;
    for(auto s:son[p])dfs(s);
    rid[p]=cnt;
}

void down(int p)
{
    if(tree[p]==-1)return;
    tree[p<<1]=tree[p<<1|1]=tree[p];
    tree[p]=-1;
}
void update(int p,int l,int r,int x,int y,int c)
{
    if(x<=l&&r<=y)
    {
        tree[p]=c;
        return;
    }
    down(p);
    int mid=(l+r)>>1;
    if(x<=mid)update(p<<1,l,mid,x,y,c);
    if(y>mid)update(p<<1|1,mid+1,r,x,y,c);
}

int query(int p,int l,int r,int x)
{
    if(l==r)return tree[p];
    down(p);
    int mid=(l+r)>>1;
    if(x<=mid)return query(p<<1,l,mid,x);
    else return query(p<<1|1,mid+1,r,x);
}


int main()
{
    int T,t=1;
    scanf("%d",&T);
    while(T--)
    {
        int n,u,v,root,m;
        cnt=0;
        scanf("%d",&n);
        build(1,1,n);
        for(int i=1;i<=n;i++)son[i].clear(),notroot[i]=0;
        for(int i=1;i<n;i++)scanf("%d%d",&u,&v),son[v].push_back(u),notroot[u]=1;
        for(int i=1;i<=n;i++)if(!notroot[i])root=i;
        dfs(root);
        scanf("%d",&m);
        printf("Case #%d:\n",t++);
        while(m--)
        {
            char op;
            int x,y;
            cin>>op>>x;
            if(op=='C')printf("%d\n",query(1,1,n,lid[x]));
            else scanf("%d",&y),update(1,1,n,lid[x],rid[x],y);
        }

    }
    return 0;
}
View Code

hdu4553，区间合并+多个lazy，题面的单引号是中文符号的(直接交会wa)，但是教我做人的是lazy，苦思冥想（wa）了很久还是把一个lazy改成了三个

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
struct node
{
    int l,r,cnt,len;
}s[maxn<<2],s2[maxn<<2];
//s存屌丝，s2存女神，l是左区间起非0数量，r是右区间起非0数量，cnt是区间内最长非0数量，len是区间长度
//单点1表示还有空，0表示已预约 
int col[maxn<<2],col2[maxn<<2],col3[maxn<<2];  //1屌丝2女神3学习 

void build(int p,int l,int r)
{
    s[p].r=s2[p].r=s[p].l=s2[p].l=s[p].len=s2[p].len=s[p].cnt=s2[p].cnt=r-l+1;
    col[p]=col2[p]=col3[p]=0;
    if(l==r)return;
    int mid=(r+l)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}

void up(int p)
{
    s[p].l=s[p<<1].l;
    if(s[p<<1].l==s[p<<1].len)s[p].l+=s[p<<1|1].l;
    s[p].r=s[p<<1|1].r;
    if(s[p<<1|1].r==s[p<<1|1].len)s[p].r+=s[p<<1].r;
    s[p].cnt=max(max(s[p<<1].cnt,s[p<<1|1].cnt),s[p<<1].r+s[p<<1|1].l);

    s2[p].l=s2[p<<1].l;
    if(s2[p<<1].l==s2[p<<1].len)s2[p].l+=s2[p<<1|1].l;
    s2[p].r=s2[p<<1|1].r;
    if(s2[p<<1|1].r==s2[p<<1|1].len)s2[p].r+=s2[p<<1].r;
    s2[p].cnt=max(max(s2[p<<1].cnt,s2[p<<1|1].cnt),s2[p<<1].r+s2[p<<1|1].l);
}

void down(int p,int l,int r)
{

    if(col3[p])
    {
        int mid=(l+r)>>1;
        s[p<<1].l=s[p<<1].r=s[p<<1].cnt=s[p<<1].len;
        s[p<<1|1].l=s[p<<1|1].r=s[p<<1|1].cnt=s[p<<1|1].len;
        s2[p<<1].l=s2[p<<1].r=s2[p<<1].cnt=s2[p<<1].len;
        s2[p<<1|1].l=s2[p<<1|1].r=s2[p<<1|1].cnt=s2[p<<1|1].len;

        col3[p<<1]=col3[p<<1|1]=col3[p];
        col2[p<<1]=col2[p<<1|1]=0;
        col[p<<1]=col[p<<1|1]=0;
        col3[p]=0;
    }
    if(col2[p])
    {
        s[p<<1].l=s[p<<1].r=s[p<<1].cnt=0;
        s[p<<1|1].l=s[p<<1|1].r=s[p<<1|1].cnt=0;
        s2[p<<1].l=s2[p<<1].r=s2[p<<1].cnt=0;
        s2[p<<1|1].l=s2[p<<1|1].r=s2[p<<1|1].cnt=0;

        col2[p<<1]=col2[p<<1|1]=col2[p];
        col[p<<1]=col[p<<1|1]=0;
        col2[p]=0;
    }
    if(col[p])
    {
        s[p<<1].l=s[p<<1].r=s[p<<1].cnt=0;
        s[p<<1|1].l=s[p<<1|1].r=s[p<<1|1].cnt=0;

        col[p<<1]=col[p<<1|1]=col[p];
        col[p]=0;
    }
}

void modify(int p,int l,int r,int x,int y,int op)
{
    if(x<=l&&r<=y)
    {
        if(col[p]!=-1)down(p,l,r);
        if(op==1)
        {
            s[p].l=s[p].r=s[p].cnt=0;
            col[p]=1;
        }
        else if(op==2)
        {
            s[p].l=s[p].r=s[p].cnt=0;
            s2[p].l=s2[p].r=s2[p].cnt=0;
            col2[p]=1;
        }
        else
        {
            s[p].l=s[p].r=s[p].cnt=s[p].len;
            s2[p].l=s2[p].r=s2[p].cnt=s2[p].len;
            col3[p]=1;
        }
        return;
    }
    down(p,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)modify(p<<1,l,mid,x,y,op);
    if(y>mid)modify(p<<1|1,mid+1,r,x,y,op);
    up(p);
}

int query(int p,int l,int r,int len,int op)
{
    if(l==r)return l;  //查询刚好有len的位置 
    int mid=(l+r)>>1;
    down(p,l,r);
    if(op==1)
    {
        if(s[p<<1].cnt>=len)return query(p<<1,l,mid,len,op);
        else if(s[p<<1].r+s[p<<1|1].l>=len)return mid-s[p<<1].r+1;
        else return query(p<<1|1,mid+1,r,len,op);
    }
    else if(op==2)
    {
        if(s2[p<<1].cnt>=len)return query(p<<1,l,mid,len,op);
        else if(s2[p<<1].r+s2[p<<1|1].l>=len)return mid-s2[p<<1].r+1;
        else return query(p<<1|1,mid+1,r,len,op);
    }
}

int main()
{
    int T,cas=1;
    scanf("%d",&T);
    while(T--)
    {
        printf("Case %d:\n",cas++);
        int n,q,qt;
        scanf("%d%d",&n,&q);
        build(1,1,n);
        while(q--)
        {
            char op[30];
            scanf("%s%d",op,&qt);
            if(op[0]=='D')
            {
                if(s[1].cnt<qt)
                    printf("fly with yourself\n");
                else
                {
                    int ans=query(1,1,n,qt,1);
                    printf("%d,let's fly\n",ans);
                    modify(1,1,n,ans,ans+qt-1,1);
                }
            }
            else if(op[0]=='N')
            {
                if(s[1].cnt<qt)
                {
                    if(s2[1].cnt<qt)printf("wait for me\n");
                    else
                    {
                        int ans=query(1,1,n,qt,2);
                        printf("%d,don't put my gezi\n",ans);
                        modify(1,1,n,ans,ans+qt-1,2);
                    }
                }
                else
                {
                    int ans=query(1,1,n,qt,1);
                    printf("%d,don't put my gezi\n",ans);
                    modify(1,1,n,ans,ans+qt-1,2);
                }
            }
            else
            {
                int qt2;
                scanf("%d",&qt2);
                modify(1,1,n,qt,qt2,3);
                printf("I am the hope of chinese chengxuyuan!!\n");
            }
        }
    }
    return 0;
}
View Code

poj2828，单点更新，从后往前要求依次满足，想排第二个变成排剩余空位的第二个，二分query

#include<iostream>
#include<stdio.h>
using namespace std;
const int maxn=2e5+10;
int s[maxn<<2],col[maxn<<2];
void up(int p)
{
    s[p]=s[p<<1]+s[p<<1|1];
}
void build(int p,int l,int r)
{
    s[p]=r-l+1;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
void modify(int p,int l,int r,int x)
{
    if(l==r)
    {
        s[p]=0;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)modify(p<<1,l,mid,x);
    else modify(p<<1|1,mid+1,r,x);
    up(p);
}

int query(int p,int l,int r,int pos)
{
    //s[p]--;
    if(l==r)return l;
    else
    {
        int mid=(l+r)>>1;
        if(pos<=s[p<<1])return query(p<<1,l,mid,pos);
        else return query(p<<1|1,mid+1,r,pos-s[p<<1]);
    }
}

int per[maxn]={0},val[maxn]={0},res[maxn]={0};
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        build(1,1,n);
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&per[i],&val[i]);
        }
        for(int i=n-1;i>=0;i--)
        {
            int ans=query(1,1,n,per[i]+1);
            res[ans]=val[i];
            modify(1,1,n,ans);
        }
        for(int i=1;i<=n;i++)
        {
            if(i!=n)printf("%d ",res[i]);
            else printf("%d\n",res[i]);
        }
    }
    return 0;
}
View Code

hdu4521，求每个数间距大于d的最长上升子序列长度，s[i]表示值为i的并且以其结束的最长上升序列是多少。每次转移的时候，查询比当前值小的最大值就可以了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int s[maxn<<2];
void up(int p)
{
    s[p]=max(s[p<<1],s[p<<1|1]);
}

void modify(int p,int l,int r,int x,int c)
{
    if(l==r)
    {
        s[p]=c;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)modify(p<<1,l,mid,x,c);
    else modify(p<<1|1,mid+1,r,x,c);
    up(p);
}
int query(int p,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)return s[p];
    int mid=(l+r)>>1,res=0;
    if(x<=mid)res=max(res,query(p<<1,l,mid,x,y));
    if(y>mid)res=max(res,query(p<<1|1,mid+1,r,x,y));
    return res;
}

int main()
{
    int n,d;
    while(scanf("%d%d",&n,&d)!=EOF)
    {
        memset(s,0,sizeof s);
        int a[maxn]={0},maxl=0,w[maxn]={0};
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]>maxl)maxl=a[i];
        }
        int ans=0;
        for(int i=0;i<n;i++)
        {

            if(i-d-1>=0)modify(1,0,maxl,a[i-d-1],w[i-d-1]);
            if(a[i]>0)w[i]=query(1,0,maxl,0,a[i]-1)+1;
            else w[i]=1;
            ans=max(ans,w[i]);

        }
        printf("%d\n",ans);
    }
    return 0;
}
View Code

cf round9,D，加点，删点，找严格大于(x,y)的点，优先选x较小的，再选y较小的。线段树查询的每个点都是一个set。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
const int maxn=2e5+10;
set<int> s2[maxn<<2];
int s[maxn<<2],temp[maxn];
void up(int p)
{
    s[p]=max(s[p<<1],s[p<<1|1]);
}
void build(int p,int l,int r)
{
    s[p]=-1;
    s2[p].clear();
    if(l==r)return;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
void update(int p,int l,int r,int x,int y,int v)
{
    if(l==r)
    {
        if(v==1)
        {
            s[p]=max(s[p],y);
            s2[x].insert(y);
        }
        else
        {
            s2[x].erase(y);
            if(!s2[x].size())s[p]=-1;
            else s[p]=*(--s2[x].end());
        }
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)update(p<<1,l,mid,x,y,v);
    else update(p<<1|1,mid+1,r,x,y,v);
    up(p);
}

int query(int p,int l,int r,int x,int y)
{
    if(r<=x||s[p]<=y)return -1;  //如果r<x||s[p]<y，查询的时候query(1,1,len,pos+1,op[i].y+1);
    if(l==r)return l;
    int mid=(l+r)>>1;
    if(x<=mid)
    {
        int tmp=query(p<<1,l,mid,x,y);
        if(tmp!=-1)return tmp;
        return query(p<<1|1,mid+1,r,x,y);
    }
    else return query(p<<1|1,mid+1,r,x,y);
}

struct node
{
    int x,y;
    char ch[20];
}op[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s %d %d",op[i].ch,&op[i].x,&op[i].y);
        temp[i]=op[i].x;
    }
    sort(temp+1,temp+1+n);
    int len=unique(temp+1,temp+1+n)-temp-1;
    build(1,1,len);
    for(int i=1;i<=n;i++)
    {
        int pos=lower_bound(temp+1,temp+1+len,op[i].x)-temp;
        if(op[i].ch[0]=='a')update(1,1,len,pos,op[i].y,1);
        else if(op[i].ch[0]=='r')update(1,1,len,pos,op[i].y,-1);
        else
        {
            if(pos==len+1)printf("-1\n");
            else
            {
                int tmp=query(1,1,len,pos,op[i].y);
                if(tmp==-1)printf("-1\n");
                else
                {
                    set<int>::iterator it=s2[tmp].upper_bound(op[i].y);
                    if(it==s2[tmp].end())printf("-1\n");
                    else printf("%d %d\n",temp[tmp],*it);
                }
            }
        }
    }
    return 0;
}
View Code

树状数组

学习链接：https://www.cnblogs.com/xenny/p/9739600.html

change里如果是0会死循环

单点更新区间查询

#include <iostream>
using namespace std;
const int MAX_N=10010;
int C[MAX_N];
int n;
int lowbit(int x)
{
    return x & (-x);  //可以写成 x&((~x)+1)
}
int getsum(int x)//求sum[1,x]
{
    int res=0;
    for(;x;x-=lowbit(x))
    {
        res+=C[x];
    }
    return res;
}
void change(int x,int c)  //第x位+c
{
    for(;x<=n;x+=x & (-x))
    {
        C[x]+=c;
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int d;
        cin>>d;
        change(i,d);
    }
    for(int i=1;i<=n;i++)
    {
        cout<<getsum(i)<<" ";
    }
    return 0;
}

//[x,y]等于[1,y]减去[1,x-1],getsum(y)-getsum(x-1)
View Code

区间更新单点查询

//要求的是a[]，建立是数组是d[]，求a[i]用get计算d[1,i]
int n,m;
int a[50005] = {0},c[50005]; //对应原数组和树状数组
int lowbit(int x)
{
    return x&(-x);
}
void updata(int i,int k)//在i位置加上k
{
    while(i <= n)
    {
        c[i] += k;
        i += lowbit(i);
    }
}


int getsum(int i)//求D[1 - i]的和，即A[i]值
{
    int res = 0;
    while(i > 0)
    {
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}


int main()
{
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        cin>>a[i];
        updata(i,a[i] - a[i-1]);   //输入初值的时候，也相当于更新了值
    }

    //[x,y]区间内加上k
    updata(x,k);    //A[x] - A[x-1]增加k
    updata(y+1,-k);        //A[y+1] - A[y]减少k

    //查询i位置的值
    int sum = getsum(i);

    return 0;
}
View Code

区间更新区间查询

int n,m;
int a[50005] = {0};
int sum1[50005];    //(D[1] + D[2] + ... + D[n])
int sum2[50005];    //(1*D[1] + 2*D[2] + ... + n*D[n])

//比如说ans[3]，=3*d1+2*d2+d3
int lowbit(int x){
    return x&(-x);
}


void updata(int i,int k){
    int x = i;    //因为x不变，所以得先保存i值
    while(i <= n){
        sum1[i] += k;
        sum2[i] += k * (x-1);
        i += lowbit(i);
    }
}


int getsum(int i){        //求前缀和
    int res = 0, x = i;
    while(i > 0){
        res += x * sum1[i] - sum2[i];
        i -= lowbit(i);
    }
    return res;
}


int main(){
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        updata(i,a[i] - a[i-1]);   //输入初值的时候，也相当于更新了值
    }


    //[x,y]区间内加上k
    updata(x,k);    //A[x] - A[x-1]增加k
    updata(y+1,-k);        //A[y+1] - A[y]减少k


    //求[x,y]区间和
    int sum = getsum(y) - getsum(x-1);


    return 0;
}
View Code

学号前a的人中，排名前b的有多少？询问按学号排序，每次加入到询问的学号，树状数组存排名第i的数在当前是否已加1/0

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,C[maxn],a[maxn],ans[maxn];
struct Node
{
    int a,b,id;
}node[maxn];

bool cmp(Node a,Node b)
{
    return a.a<b.a;
}

int lowbit(int x)
{
    return x&(-x);
}
int getsum(int x)
{
    int res=0;
    for(;x;x-=lowbit(x))
    res+=C[x];
    return res;
}
void change(int x,int c)
{
    for(;x<=n;x+=lowbit(x))
    C[x]+=c;
}

int main()
{
    int q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&node[i].a,&node[i].b);
        node[i].id=i;
    }
    node[0].id=0;
    sort(node+1,node+1+q,cmp);
    int j=1;
    for(int i=1;i<=q;i++)
    {
        for(;j<=node[i].a;j++)
        change(a[j],1);
        ans[node[i].id]=getsum(node[i].b);
    }
    for(int i=1;i<=q;i++)
    printf("%d\n",ans[i]);
    return 0;
}
View Code

树状数组维护区间最值，只支持末端添加

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int c[maxn],a[maxn];
int lowbit(int x)
{
    return x&(-x);
}

void change(int r)  //只支持末端修改 
{
    c[r]=a[r];
    for(int i=1;i<lowbit(r);i<<=1)
        c[r]=max(c[r],c[r-i]);
}

int getmax(int l,int r)  //[L,R]内求max 
{
    int ret=a[r];
    while(l<=r)
    {
        ret=max(ret,a[r]);
        for(--r;r-l>=lowbit(r);r-=lowbit(r))
            ret=max(ret,c[r]);
    }
    return ret;
}

int main()
{
    int m,mod,num=1,ans=0;
    scanf("%d%d",&m,&mod);
    while(m--)
    {
        getchar();
        char ch;
        int l;
        scanf("%c %d",&ch,&l);
        if(ch=='Q')
        {
            ans=getmax(num-l,num);
            printf("%d\n",ans);
        }
        else
        {
            a[num]=(l+ans)%mod;
            change(num);
            num++;
        }
    }
    return 0;
}
View Code

二维树状数组用一维做，2019南京网络赛A

https://nanti.jisuanke.com/t/41298

#include<bits/stdc++.h>
using namespace std;
#define pr pair<int,long long>
const int maxn=1e6+5;
int n,m,p;

vector<pr>inx[maxn];
struct qry
{
    int y1,y2,id;
};
vector<qry> add[maxn],mov[maxn];
long long ans[maxn],b[maxn],num[maxn];


long long calc(int x,int y)
{
    x=x-n/2-1;
    y=y-n/2-1;
    long long t=max(abs(x),abs(y));
    long long res;
    if(x>=y) res=1ll*n*n-4*t*t-2*t-x-y;
    else res=1ll*n*n-4*t*t+2*t+x+y;
    return res;
}

inline void prework()
{
    scanf("%d%d%d",&n,&m,&p);
    for(int i=0;i<=n;i++)
    {
        add[i].clear();
        mov[i].clear();
        inx[i].clear();
    }

    for(int i=1;i<=n/2;i++)
        num[i]=num[i-1]+4*(n-2*(i-1))-4;
    num[n/2+1]=num[n/2]+1;
    for(int i=1;i<=m;i++)
    {
        int x1,y1;
        long long val;
        scanf("%d%d",&x1,&y1);
        val=calc(x1,y1);
        int d=0;
        while(val>0)
        {
            d+=val%10;
            val/=10;
        }
        inx[x1].push_back(make_pair(y1,d));
    }
    for(int i=1;i<=p;i++)
    {
        int x1,x2,y1,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        mov[x1-1].push_back(qry{y1,y2,i});
        add[x2].push_back(qry{y1,y2,i});
    }
}

inline void update(int i,long long x)
{
    while(i<=n)
    {
        b[i]+=x;
        i+=i&-i;
    }
}

inline long long sum(int i)
{
    long long ret=0;
    while(i)
    {
        ret+=b[i];
        i-=i&-i;
    }
    return ret;
}


inline void mainwork()
{
    memset(b,0,sizeof(b));
    memset(ans,0,sizeof(ans));
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<inx[i].size();j++)
        {
            pr d=inx[i][j];
            update(d.first,d.second);
        }
        for(int j=0;j<add[i].size();j++)
        {
            int y1,y2,id;
            id=add[i][j].id;
            y1=add[i][j].y1;
            y2=add[i][j].y2;
            ans[id]+=sum(y2)-sum(y1-1);
        }
        for(int j=0;j<mov[i].size();j++)
        {
            int y1,y2,id;
            id=mov[i][j].id;
            y1=mov[i][j].y1;
            y2=mov[i][j].y2;
            ans[id]-=sum(y2)-sum(y1-1);
        }
    }
}
inline void print()
{
    for(int i=1;i<=p;i++)
    printf("%lld\n",ans[i]);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        prework();
        mainwork();
        print();
    }
    return 0;
}
View Code

多校九求射线交点+1，边界无点。把横着的线变成左边入、右边出两个点，树状数组维护离散话后的y的数量，将竖着的射线从左到右进行查询。

http://acm.hdu.edu.cn/showproblem.php?pid=6681

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int c[maxn],n,m,k,cntp,cnts;
int lowbit(int x)
{
    return x&-x;
}
vector<int>v;
struct Seg
{
    int x,y1,y2;
    bool operator <(Seg other) const{
        return x<other.x;
    }
}seg[maxn];

struct Point
{
    int x,y,val;
    bool operator <(Point other) const{
        return x<other.x;
    }
}point[maxn];

int getid(int y)
{
    return lower_bound(v.begin(),v.end(),y)-v.begin()+1;
}

void update(int x,int val)
{
    for(int i=x;i<=getid(m);i+=lowbit(i))
    {
        c[i]+=val;
    }
}

int query(int x)
{
    int res=0;
    for(;x;x-=lowbit(x))
    {
        res+=c[x];
    }
    return res;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(c,0,sizeof(c));
        v.clear();

        scanf("%d%d%d",&n,&m,&k);
        v.push_back(0);
        v.push_back(m);
        cntp=0,cnts=0;
        for(int i=1;i<=k;i++)
        {
            int x,y;
            char dir[2];
            scanf("%d%d%s",&x,&y,dir);
            v.push_back(y);
            if(dir[0]=='L')
            {
                point[cntp++]=Point{0,y,1};
                point[cntp++]=Point{x,y,-1};
            }
            else if(dir[0]=='R')
            {
                point[cntp++]=Point{x,y,1};
                point[cntp++]=Point{n,y,-1};
            }
            else if(dir[0]=='U')
            {
                seg[cnts++]=Seg{x,y,m};
            }
            else
            {
                seg[cnts++]=Seg{x,0,y};
            }
        }
        sort(v.begin(),v.end());
        //m=getrid(m);
        sort(seg,seg+cnts);
        sort(point,point+cntp);
        for(int i=0;i<cnts;i++)
        {
            seg[i].y1=getid(seg[i].y1);
            seg[i].y2=getid(seg[i].y2);
        }
        for(int i=0;i<cntp;i++)
        {
            point[i].y=getid(point[i].y);
        }
        int pos=0,sum=0;
        for(int i=0;i<cnts;i++)
        {
            while(point[pos].x<seg[i].x)
            {
                update(point[pos].y,point[pos].val);
                pos++;
            }
            sum+=query(seg[i].y2)-query(seg[i].y1-1);
        }
        printf("%d\n",sum+1);
    }
    return 0;
}
View Code

树状数组高级应用sumseek()，寻找部分和为k的第一个位置

int sumseek (int k)//寻找部分和为k的第一个位置
{
    int ans = 0, sum = 0, i;
    for (i = 18; i >= 0; i--)
    {
        ans += (1 << i);
        if (ans >= n || sum + bit[ans] >= k) ans -= (1 << i);
        else sum += bit[ans];
    }
    return ans + 1;
}
View Code

二维树状数组

单点更新区间查询

#include <iostream>
using namespace std;
const int MAX_N=810;
int C[MAX_N][MAX_N];
int n;
int lowbit(int x)
{
    return x&(-x);
}
void change(int i,int j,int delta)
{
    for(int x=i;x<=n;x+=lowbit(x))
    {
        for(int y=j;y<=n;y+=lowbit(y))
        {
            C[x][y]+=delta;
        }
    }
}
int getsum(int i,int j)
{
    int res=0;
    for(int x=i;x;x-=lowbit(x))
    {
        for(int y=j;y;y-=lowbit(y))
        {
            res+=C[x][y];
        }
    }
    return res;
}

//子矩阵(x1,y1)~(x2,y2)的和
//ans=sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1);
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int d;
            cin>>d;
            change(i,j,d);
        }
    }
    int x,y;
    cin>>x>>y;
    cout<<getsum(x,y)<<endl;

    return 0;
}
View Code

 区间更新单点查询

#include<bits/stdc++.h>
using namespace std;
const int maxn=1050;
int c[maxn][maxn];
int n;
int lowbit(int x)
{
    return x&(-x);
}
void change(int i,int j)
{
    for(int x=i;x<=n;x+=lowbit(x))
    {
        for(int y=j;y<=n;y+=lowbit(y))
        {
            c[x][y]=1-c[x][y];
        }
    }
}
int getsum(int i,int j)
{
    int res=0;
    for(int x=i;x;x-=lowbit(x))
    {
        for(int y=j;y;y-=lowbit(y))
        {
            res+=c[x][y];
        }
    }
    return res;
}
int main()
{
    int m;
    cin>>n>>m;
    while(m--)
    {
        char ch;
        cin>>ch;
        if(ch=='C')
        {
            int x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            change(x2+1,y2+1);
            change(x1,y1);
            change(x2+1,y1);
            change(x1,y2+1);
        }
        else
        {
            int x,y;
            cin>>x>>y;
            int ans=getsum(x,y)%2;
            cout<<ans<<endl;
        }
    }
    return 0;
}
View Code

数据离散化

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int maxn=10010;
int num[maxn];
int temp[maxn];
int n;
map<int,int>mp;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>num[i];
        temp[i]=num[i];
    }
    sort(temp,temp+n);
    int m=unique(temp,temp+n)-temp;
    for(int i=0;i<m;i++)
    {
        mp[temp[i]]=i+1;
    }
    for(int i=0;i<n;i++)
    {
        cout<<mp[num[i]]<<" ";
    }
    return 0;
}

// 5 1 11 111 1111 11111输出 1 2 3 4 5
// 5 1111 111 111 11 11输出3 2 2 1 1
View Code

 数组[1,n]的离散化

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5;
int num[maxn];
int temp[maxn];
int n;
map<int,int>mp;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>num[i];
        temp[i]=num[i];
    }
    sort(temp+1,temp+1+n);
    int m=unique(temp+1,temp+1+n)-temp-1;
    for(int i=1;i<=m;i++)
    {
        mp[temp[i]]=i;
    }
    for(int i=1;i<=n;i++)
    {
        cout<<mp[num[i]]<<" ";
    }
    return 0;
}
View Code

自制区间离散，一维n个区间

#include<bits/stdc++.h>
using namespace std;
const int maxn=10010;
int numl[maxn],numr[maxn];
int temp[maxn<<1];
int n;
map<int,int> mp;
int main()
{
    int m;
    cin>>n>>m;//m是区间max 
    for(int i=1;i<=n;i++)
    {
        cin>>numl[i]>>numr[i];
        temp[i]=numl[i];
        temp[i+n]=numr[i];
    }
    sort(temp+1,temp+1+n+n);
    int len=unique(temp+1,temp+1+n+n)-temp-1;
    for(int i=1;i<=len;i++)
    {
        mp[temp[i]]=i;
    }

    for(int i=1;i<=n;i++)
    {
        cout<<mp[numl[i]]<<" "<<mp[numr[i]]<<endl;
    }
    return 0;
}
/*
5 100
20 35
5 30
50 80
31 60
55 85
输出：
2 5
1 3
6 9
4 8
7 10
*/
View Code

离散化+树状数组求逆序数

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5;
int num[maxn];
int temp[maxn];
int n;
map<int,int>mp;

int C[maxn];
int lowbit(int x)
{
    return x&(-x);
}
int getsum(int x)
{
    int res=0;
    for(;x;x-=lowbit(x))
    {
        res+=C[x];
    }
    return res;
}
void change(int x,int c)
{
    for(;x<=n;x+=lowbit(x))
    {
        C[x]+=c;
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num[i]);
        temp[i]=num[i];
    }
    sort(temp+1,temp+1+n);
    int m=unique(temp+1,temp+1+n)-temp-1;
    for(int i=1;i<=m;i++)
    {
        mp[temp[i]]=i;
    }
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        change(mp[num[i]],1);  //查询前更新 
        int tmp=i-getsum(mp[num[i]]);  //getsum是找目前有几个比mp[num[i]]小的，i-getsum()就可以得知比它大的有几个 
        ans+=tmp;
        //cout<<mp[num[i]]<<" ";
    }
    printf("%lld\n",ans);
    return 0;
}
View Code

离散化+线段树，查询区间内是否有0（ans+1），更改区间值都为1 ，一维区间覆盖问题

如果map超时用unordered_map或者改成

int l=lower_bound(temp+1,temp+1+len,numl[i])-temp;
int r=lower_bound(temp+1,temp+1+len,numr[i])-temp;

#include<bits/stdc++.h>
using namespace std;
const int maxn=10050;
int numl[maxn],numr[maxn];
int temp[maxn<<1];
int n;
map<int,int> mp;

int s[maxn<<3],col[maxn<<3];//点数*4
void up(int p)
{
    s[p]=min(s[p<<1],s[p<<1|1]);
}
void down(int p,int l,int r)
{
    if(col[p])
    {
        int mid=(l+r)>>1;
        s[p<<1]=max(s[p<<1],col[p]);
        s[p<<1|1]=max(s[p<<1|1],col[p]);
        col[p<<1]=max(col[p<<1],col[p]);
        col[p<<1|1]=max(col[p<<1|1],col[p]);
        col[p]=0;
    }
}

void modify(int p,int l,int r,int x,int y,int c)
{
    if(x<=l&&r<=y)
    {
        s[p]=c;
        col[p]=c;
        return;
    }
    down(p,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)modify(p<<1,l,mid,x,y,c);
    if(y>mid)modify(p<<1|1,mid+1,r,x,y,c);
    up(p);
}

int query(int p,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        return s[p];
    }
    down(p,l,r);
    int mid=(l+r)>>1,res=1;
    if(x<=mid)res=min(res,query(p<<1,l,mid,x,y));
    if(y>mid)res=min(res,query(p<<1|1,mid+1,r,x,y));
    return res;
}



int main()
{
    int m;
    cin>>n>>m;//m是区间max 
    for(int i=1;i<=n;i++)
    {
        cin>>numl[i]>>numr[i];
        temp[i]=numl[i];
        temp[i+n]=numr[i];
    }
    sort(temp+1,temp+1+n+n);
    int len=unique(temp+1,temp+1+n+n)-temp-1;
    for(int i=1;i<=len;i++)
    {
        mp[temp[i]]=i;
    }

    int ans=0;
    for(int i=n;i>=1;i--)
    {
        //cout<<mp[numl[i]]<<" "<<mp[numr[i]]<<endl;
        if(query(1,1,len,mp[numl[i]],mp[numr[i]])==0)
            ans++,modify(1,1,len,mp[numl[i]],mp[numr[i]],1);
    }
    cout<<ans<<endl;
    return 0;
}
View Code

扫描线

面积并

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
struct node
{
    int l,r,cover,len;
}tree[maxn<<3];

struct Line
{
    int x,y1,y2;
    int flag;
}line[maxn<<1];

int temp[maxn<<1];
unordered_map<int,int> mp,mp2;//改成unordered map就不超时了 

void build(int p,int l,int r)
{
    tree[p].l=l;
    tree[p].r=r;
    tree[p].cover=0;
    tree[p].len=0;
    if(l+1==r)return;
    int mid=(l+r+1)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid,r);  //区间树 
}

bool cmp(Line a,Line b)
{
    if(a.x==b.x)return a.y1<b.y1;
    else return a.x<b.x;
}

void up(int p,int l,int r)
{
    if(tree[p].cover>0) tree[p].len=mp2[tree[p].r]-mp2[tree[p].l];
    else if(l==r-1) tree[p].len=0;  //没有这句tree要再开*2 
    else tree[p].len=tree[p<<1].len+tree[p<<1|1].len;
}

void modify(int p,int l,int r,int x,int y,int flag)
{
    if(x<=l&&r<=y)
    {
        tree[p].cover+=flag;
        up(p,l,r);
        return;
    }
    int mid=(l+r+1)>>1;
    if(x<mid)modify(p<<1,l,mid,x,y,flag);
    if(y>mid)modify(p<<1|1,mid,r,x,y,flag);
    up(p,l,r);
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        line[i].x=x1;
        line[i].y1=y1;
        line[i].y2=y2;
        line[i].flag=1;
        line[i+n].x=x2;
        line[i+n].y1=y1;
        line[i+n].y2=y2;
        line[i+n].flag=-1;
        temp[i]=y1;
        temp[i+n]=y2;
    }
    sort(temp+1,temp+1+n*2);
    sort(line+1,line+1+n*2,cmp);
    int tot=unique(temp+1,temp+1+n*2)-temp-1;

    for(int i=1;i<=tot;i++)
    {
        mp[temp[i]]=i;
        mp2[i]=temp[i];
    }
    build(1,1,tot);
    long long ans=0;
    for(int i=1;i<=n*2-1;i++)
    {
        modify(1,1,tot,mp[line[i].y1],mp[line[i].y2],line[i].flag);
        ans+=1LL*(line[i+1].x-line[i].x)*tree[1].len;
    }
    printf("%lld\n",ans);
    return 0;
}
View Code

周长并，poj1177，hdu1828

题目是过了但是这组数据没过，

3

0 0 1 2

0 2 1 4

1 1 2 3

output应该是12

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
struct node
{
    int l,r,cover,len,num;
    int lflag,rflag;
}tree[maxn<<3];

struct Line
{
    int x,y1,y2;
    int flag;
}line[maxn<<1];

int temp[maxn<<1];
unordered_map<int,int> mp,mp2;

void build(int p,int l,int r)
{
    tree[p].l=l;
    tree[p].r=r;
    tree[p].cover=0;
    tree[p].len=0;
    tree[p].num=0;
    tree[p].lflag=tree[p].rflag=0;
    if(l+1==r)return;
    int mid=(l+r+1)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid,r);
}

void up(int p,int l,int r)
{
    if(tree[p].cover>0)
    {
        tree[p].len=mp2[tree[p].r]-mp2[tree[p].l];
        tree[p].num=1;
        tree[p].lflag=tree[p].rflag=1;
    }
    else if(l+1==r)
    {
        tree[p].len=0,tree[p].num=0;
        tree[p].lflag=tree[p].rflag=0;
    }
    else
    {
        tree[p].len=tree[p<<1].len+tree[p<<1|1].len;
        tree[p].num=tree[p<<1].num+tree[p<<1|1].num;
        if(tree[p<<1].rflag&&tree[p<<1|1].lflag)
        {
            tree[p].num--;
        }
        tree[p].lflag=tree[p<<1].lflag;
        tree[p].rflag=tree[p<<1|1].rflag;
    }
}

void modify(int p,int l,int r,int x,int y,int flag)
{
    if(x<=l&&r<=y)
    {
        tree[p].cover+=flag;
        up(p,l,r);
        return;
    }
    int mid=(l+r+1)>>1;
    if(x<mid)modify(p<<1,l,mid,x,y,flag);
    if(y>mid)modify(p<<1|1,mid,r,x,y,flag);
    up(p,l,r);
}

bool cmp(Line a,Line b)
{
    if(a.x==b.x)return a.y1<b.y1;
    else return a.x<b.x;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        line[i].x=x1;
        line[i].y1=y1;
        line[i].y2=y2;
        line[i].flag=1;
        line[i+n].x=x2;
        line[i+n].y1=y1;
        line[i+n].y2=y2;
        line[i+n].flag=-1;
        temp[i]=y1;
        temp[i+n]=y2;
    }
    sort(temp+1,temp+1+n*2);
    sort(line+1,line+1+n*2,cmp);
    int tot=unique(temp+1,temp+1+n*2)-temp-1;
    for(int i=1;i<=tot;i++)
    {
        mp[temp[i]]=i;
        mp2[i]=temp[i];
    }
    build(1,1,tot);
    long long ans=0,last=0;
    for(int i=1;i<=n*2;i++)
    {
        modify(1,1,tot,mp[line[i].y1],mp[line[i].y2],line[i].flag);
        ans+=abs(tree[1].len-last);
        last=tree[1].len;
        if(i!=n*2) ans+=1LL*tree[1].num*2*(line[i+1].x-line[i].x);
    }
    printf("%lld\n",ans);
    return 0;
}
View Code

主席树

...

待补：hdu1394，hdu2795，uva10810，poj2155，poj1195，hdu1823，poj1195，hdu2688，hdu1892，hdu2227，hdu1255，hdu1542，hdu3887，hdu1541，hdu2642，hdu3030，hdu1540，hdu3016，hdu3308，hdu2871，hdu3667，poj1436，51nod1199，hut4302，hdu2461，hdu4325，hdu433，hdu4339，hdu3874，hdu4366，hdu4288，poj2750，poj2029，xtu1170，bzoj1095，hdu4476，hdu4456，hdu4521

线段树：

hdu1166，hdu1754，poj3468，poj2528，hdu1698，zoj1610，poj3264，hdu4027，hdu1540，hdu3974，hdu4578，hdu4614，hdu4553，poj1177，hdu1255，hdu1542，hdu3642

二维线段树树状数组：

cf240F，hdu1823，hdu4819，hdu5517，hysbz1452，poj1195，poj1656，poj2155，uva11297

线段树进阶：

hdu5306，hdu5316，hdu5367，hdu5592，hdu5722，hdu5828，hdu5862，hysbz1858，hysbz2957，hysbz1858，cf2957，cf500e，cf515e，cf558e，cf594d，cf609f，cf620e，cf626g，cf629d，cf635d，cf719e，cf777e，cf786b，hdu5238，hdu5239，hdu5289，hdu5324，hdu5372，hdu5412，hdu5475，hdu5493，hdu5634，hdu5700，hdu5726，hdu5877，hysbz6070，hysbz1103，hysbz329

动态开点线段树：hdu6183，cf915e

线段树离散化：hdu4325，uvalive7141，poj3277，hdu3333，lightoj1089，poj3368，zoj3612

扫描线：poj3470，poj3109，uva11990，hdu1828，hdu4419，poh2482，cf817f

rmq：hysbz1067，poj1050，poj2019，hdu3486，hdu3193，hdu2888，hdu3183

离散化题目：uva1077，uvalive3532，uvalive3809，uvalive4492，poj1151，poj1389，voj1056，voj1238

02-13 14:44
Powered by LMLPHP ©2024 区间 0.073251