K 대수 조회

K 대수 조회
시간 제한: 2 Sec 메모리 제한: 512 MB
제목 설명 은 n 개의 위치 와 m 개의 조작 이 있 습 니 다.조작 은 두 가지 가 있 는데 매번 조작 이 1a b c 의 형식 이 라면 a 번 째 위치 에서 b 번 째 위치 까지 모든 위치 에 하나의 수 c 를 추가 하 는 것 을 나타 낸다.만약 에 조작 형 이 2a b c 와 같은 형식 이 라면 a 번 째 위치 에서 b 번 째 위치 까지 c 번 째 큰 수 는 얼마 인지 물 어 보 는 것 을 나타 낸다.
입력 파일 sequence. in 에 입력 하 십시오. 첫 번 째 줄 은 n, m 입 니 다.의 미 는 제목 설명 과 같다.다음 m 줄 의 각 줄 형 태 는 1 a b c 또는 2 a b c 와 같 습 니 다.
출력 은 출력 파일 sequence. out 에서 질문 마다 k 의 대수 가 얼마 인지 대답 합 니 다.
샘플 입력 2, 5, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 2, 3.
샘플 출력
첫 번 째 조작 후 위치 1 의 수 는 1 이 고 위치 2 의 수도 1 에 불과 하 다.두 번 째 조작 후 위치 1 의 수 는 1, 2 이 고 위치 2 의 수도 1, 2 이다.세 번 째 질문 위치 1 부터 위치 1, 2 위 는 1.네 번 째 질문 위치 1 부터 위치 1 까지 1 번 째 로 큰 수 는 2 다.다섯 번 째 질문 위치 1 부터 위치 2, 3 번 째 는 1 이다.30% 의 데이터 n = m = 1000 100% 의 데이터 n, m ≤ 50000, 그리고 후 7 개 점 의 데이터 n, m 의 범 위 는 32000 에서 50000 까지 입 니 다.
출처 zjoi 2013
해제
구간 수정 요구 구간 K 가 크 면 트 리 배열 세트 의장 트 리 로 해결한다.가중치 선분 트 리 에 2 개의 값 을 저장 하고, 1 개의 s1 은 각 구간 이 몇 번 추가 되 었 는 지 를 나타 내 며, 다른 s2 는 매번 수정 작업 왼쪽 구간 의 총 계 를 나타 낸다.크기 = s1 * (x + 1) - s2.
코드

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define N 50010
#define ll long long
using namespace std;
int n,m,t1,t2,cnt,wbs[20],cyc[20],rt[N];
struct node{int lc,rc,s1,s2;}t[N*50];

class seg_tree
{
  public:
  void modify(int &x,int pre,int l,int r,int des,int val,int num)
  {
    x=pre?pre:++cnt;
    t[x]=t[pre];t[x].s1+=val;t[x].s2+=num;
    if(l==r)return;
    int mid=l+r>>1;
    if(des<=mid)modify(t[x].lc,t[pre].lc,l,mid,des,val,num);
    else modify(t[x].rc,t[pre].rc,mid+1,r,des,val,num);
  }
  int qry(int x,int pre,int l,int r,int k,int L,int R)
  {
    if(l==r)return l;
    int cnt1=0,cnt2=0,mid=l+r>>1;
    for(int i=1;i<=t1;i++)cnt1+=R*t[t[wbs[i]].rc].s1-t[t[wbs[i]].rc].s2;
    for(int i=1;i<=t2;i++)cnt2+=L*t[t[cyc[i]].rc].s1-t[t[cyc[i]].rc].s2;
    if(cnt1-cnt2>=k)
    {
      for(int i=1;i<=t1;i++)wbs[i]=t[wbs[i]].rc;
      for(int i=1;i<=t2;i++)cyc[i]=t[cyc[i]].rc;
      return qry(t[x].rc,t[pre].rc,mid+1,r,k,L,R);
    }
    for(int i=1;i<=t1;i++)wbs[i]=t[wbs[i]].lc;
    for(int i=1;i<=t2;i++)cyc[i]=t[cyc[i]].lc;
    return qry(t[x].lc,t[pre].lc,l,mid,k-cnt1+cnt2,L,R);
  }
}T2;

class bit
{
  public:
  void modify(int x,int des,int val,int num)
  {
    for(;x<=n;x+=x&-x)T2.modify(rt[x],rt[x],1,n,des,val,num);
  }
  int qry(int l,int r,int k)
  {
    int x;t1=0;t2=0;
    x=r;for(;x;x-=x&-x)wbs[++t1]=rt[x];
    x=l;for(;x;x-=x&-x)cyc[++t2]=rt[x];
    return T2.qry(rt[r],rt[l],1,n,k,l+1,r+1);
  }
}T1;

int main()
{
  int type,a,b,c;
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++)
  {
    scanf("%d%d%d%d",&type,&a,&b,&c);
    if(type==1)T1.modify(a,c,1,a),T1.modify(b,c,-1,-b-1);
    else printf("%d
",T1.qry(a-1,b,c));
  }
  return 0;
}