낙 곡 P3332 [ZJOI 2013] K 대수 조회 선분 트 리 커버 선분 트 리

제목 설명
N 개의 위치 가 있 고 M 개의 조작 이 있 습 니 다.조작 은 두 가지 가 있 습 니 다. 매번 조작 이 1a b c 의 형식 이 라면 a 번 째 위치 에서 b 번 째 위치 까지 모든 위치 에 하나의 수 c 를 추가 합 니 다. 만약 에 2a b c 형식 이 라면 a 번 째 위치 에서 b 번 째 위치 까지 문의 하고 C 번 째 큰 수 는 얼마 입 니까?
입 출력 형식
입력 형식: 첫 줄 N, M 다음 M 줄, 줄 당 1 a b c 또는 2 a b c
출력 형식: 모든 문의 결 과 를 출력 합 니 다.
입 출력 샘플
입력 샘플 \ # 1: 2 5 1 2 1 1 1 2 2 1 2 1 1 1 1 1 2 1 1 2 1 2 3 출력 샘플 \ # 1: 1 2 1 설명
[예시 설명]
첫 번 째 조작 후 위치 1 의 수 는 1 이 고 위치 2 의 수도 1 에 불과 하 다.두 번 째 조작 후 위치 1
의 수 는 1, 2 이 고 위치 2 의 수도 1, 2 이다.세 번 째 질문 위치 1 부터 위치 1, 2 위 는...
1 。 네 번 째 질문 위치 1 부터 위치 1 까지 1 번 째 로 큰 수 는 2 다.다섯 번 째 질문 위치 1 부터 위치 2, 3.
큰 수 는 1 이다.‍
N,M<=50000,N,M<=50000
a<=b<=N
1 동작 중 abs (c) < = N
2 작업 중 c < = Maxlongint
분석: 구간 k 가 큰 것 에 대해 서 는 분명히 가중치 선분 나 무 를 열 수 있 지만 구간 이 수정 되 었 기 때문에 밖 에 구간 선분 나 무 를 한 그루 더 설치 한 후에 이렇게 레이 지 는 약간 복잡 하 게 치 는 것 을 발견 했다. 몇 개의 값 을 내 려 야 할 수도 있 기 때문에 가중치 선분 나무 로 구간 선분 나 무 를 묶 으 면 된다. 사실은 첫 번 째 도 할 수 있 고 물론 splay 도 할 수 있다.그러나 도연 전체 2 점, cdq 분 치 의 문제 라 고 한다.롱 롱 으로 갈 게 요.다음 전송 표 시 는 사실 reove 를 칠 수 있 습 니 다. 선분 트 리 에 직접 넣 지 않 아 도 됩 니 다.
코드:

#include 
#include 

const int maxn=50001;
using namespace std;

struct tree{
    int l,r,llazy,rlazy;
    long long sum;
}t[maxn*400];

int x,y,c,op,cnt,n,m,i;
int root[maxn*10];

void change_tree(int &p,int l,int r,int x,int y,int k,int c)
{
    if (p==0)
    {
        cnt++;
        p=cnt;
    }
    int sum;
    t[p].sum+=(long long)(y-x+1)*k+(r-l+1)*c;
    t[p].llazy+=c;
    t[p].rlazy+=c;
    if ((l==x) && (r==y))
    {
        t[p].llazy+=k;
        t[p].rlazy+=k;
        return;
    }
    int mid=(l+r)/2;
    if (y<=mid)
    {
        sum=t[p].llazy;
        t[p].llazy=0;
        change_tree(t[p].l,l,mid,x,y,k,sum);
    }
    else
    {
        if (x>mid)
        {
            sum=t[p].rlazy;
            t[p].rlazy=0;
            change_tree(t[p].r,mid+1,r,x,y,k,sum);
        }
        else
        {
            sum=t[p].llazy;
            t[p].llazy=0;
            change_tree(t[p].l,l,mid,x,mid,k,sum);
            sum=t[p].rlazy;
            t[p].rlazy=0;
            change_tree(t[p].r,mid+1,r,mid+1,y,k,sum);
        }
    }
}

long long getsum(int &p,int l,int r,int x,int y,int c)
{
    if (p==0)
    {
        cnt++;
        p=cnt;
    }
    int sum,sm;
    t[p].sum+=(r-l+1)*c;
    t[p].llazy+=c;
    t[p].rlazy+=c;
    if ((l==x) && (r==y)) return (long long) t[p].sum;
    int mid=(l+r)/2;
    if (y<=mid)
    {
        sum=t[p].llazy;
        t[p].llazy=0;
        return (long long) getsum(t[p].l,l,mid,x,y,sum);
    }
    else
    {
        if (x>mid)
        {
            sum=t[p].rlazy;
            t[p].rlazy=0;
            return (long long) getsum(t[p].r,mid+1,r,x,y,sum);
        }
        else
        {
            sum=t[p].llazy;
            t[p].llazy=0;
            sm=t[p].rlazy;
            t[p].rlazy=0;
            return (long long) getsum(t[p].l,l,mid,x,mid,sum)+getsum(t[p].r,mid+1,r,mid+1,y,sm);
        }
    }    
}

void change(int p,int l,int r,int x,int y,int c)
{
    change_tree(root[p],1,n,x,y,1,0);
    if (l==r) return;
    int mid=(l+r)/2;
    if (c<=mid) change(p*2,l,mid,x,y,c);
           else change(p*2+1,mid+1,r,x,y,c);      
}

int ask(int p,int l,int r,int x,int y,long long k)
{
    if (l==r) return l;
    int mid=(l+r)/2;
    long long sum=getsum(root[p*2+1],1,n,x,y,0);
    if (k>sum) return ask(p*2,l,mid,x,y,k-sum);
          else return ask(p*2+1,mid+1,r,x,y,k);
}

int main()
{
    scanf("%d%d",&n,&m);        
    for (i=1;i<=m;i++)
    {
        scanf("%d%d%d",&op,&x,&y);
        if (op==1)
        {
            scanf("%d",&c);
            change(1,1,maxn,x,y,c);
        }
        else
        {       

            int k;
            scanf("%d",&k);
            printf("%d
",ask(1,1,maxn,x,y,k));
        }
    }
    return 0;
}