[예제] [선분 수]

1、 ！！！！！나 무 를 만 들 수 없 는 상황 에 주의 하 세 요 NKOJ 1321 수열 조작 문제 시간 제한: 10000 MS 공간 제한: 165536 KB
문제 설명 은 하나의 열 수 {Ai} (1 ≤ i ≤ n) 가 있다 고 가정 하고 다음 과 같은 두 가지 조작 을 지원 합 니 다. Ak 의 값 을 D 로 추가 합 니 다.(k, D 는 입력 한 수) 출력 as + as + 1 +... + At.(s, t 는 모두 입력 한 수, S ≤ T)
형식 첫 줄 의 정수 n, 두 번 째 행위 n 개의 정 수 를 입력 하여 {Ai} 의 초기 값 ≤ 10000 을 표시 합 니 다.세 번 째 행 위 는 하나의 정수 m 로 조작 수 에서 m 줄 을 연결 하 는 것 을 나타 내 고 줄 마다 하나의 조작 을 설명 하 며 다음 과 같은 두 가지 상황 이 있다. ADD k d (Ak 를 d, 1 < = k < = n, d 를 수, d 의 절대 치 는 10000 을 초과 하지 않 음 을 나타 낸다) SUM s t (출력 as +... + At)
출력 형식 이 모든 SUM 질문 에 대한 출력 결과
샘플 입력 5 1 2 3 2 4 5 SUM 1 2 SUM 1 5 ADD 1 2 SUM 1 2 SUM 1 2 SUM 1 5
샘플 출력
알림 M, N < = 100000
/ * 1. 선분 수 는 이분 사상 을 통 해 구간 관 계 를 나타 내 는 나무 구조 입 니 다. 2. 노드 수 는 최대 2n - 1 개 * /

#include
#include
using namespace std;
const int need=100003;

struct fy{int a,b,le,ri,val;}tree[need*2];//        2×n
//   {int a,b,val;}tree[need*4]i*2     ，i*2+1     ；        4×n

int a[need];
int tot=0,k,d;

void build(int x,int y)
{
    int s=++tot;
    tree[s].a=x,tree[s].b=y;
    //tree[s].val=suma[y]-suma[x-1];
    if(x1;
        build(x,(x+y)/2);
        tree[s].ri=tot+1;
        build((x+y)/2+1,y);
        tree[s].val=tree[tree[s].le].val+tree[tree[s].ri].val;
    }
    else if(x==y) tree[s].val=a[x];
}

void add_(int s)
{
    tree[s].val+=d;
    if(tree[s].le!=0&&tree[tree[s].le].a<=k&&tree[tree[s].le].b>=k) add_(tree[s].le);
    else if(tree[s].ri!=0&&tree[tree[s].ri].a<=k&&tree[tree[s].ri].b>=k) add_(tree[s].ri);
}

int sum_(int s)
{
    if(k<=tree[s].a&&tree[s].b<=d) return tree[s].val;
    int ans=0;
    if(!(tree[tree[s].le].a>d||tree[tree[s].le].bif(!(tree[tree[s].ri].a>d||tree[tree[s].ri].b/* ：
    if(k<=tree[tree[s].le].b&&tree[tree[s].le].a<=d) ans+=sum_(tree[s].le);
    if(k<=tree[tree[s].ri].b&&tree[tree[s].ri].a<=d) ans+=sum_(tree[s].ri);
               
    */
    return ans;
}
/*  

int sum_(int s)
{
    if(dtree[s].b) return 0;
    if(k<=tree[s].a&&tree[s].b<=d) return tree[s].val;
    return sum_(s<<1)+sum_((s<<1)|1);
}

*/

int main()
{
    int n;scanf("%d",&n);
    //int a;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        //suma[i]=suma[i-1]+a; 
    } 
    build(1,n);
    int m;scanf("%d",&m);
    string b;
    for(int i=1;i<=m;i++)
    {
        cin>>b;scanf("%d%d",&k,&d);
        if(b=="SUM")  printf("%d
",sum_(1));
        else if(b=="ADD") add_(1);
    }
} 

2. NKOJ 1344 인적자원 관리 시간 제한: 10000 MS 공간 제한: 65536 KB 문 제 는 특정한 회사 에 n 명의 직원 이 있 고 모든 직원 에 게 업무 능력 치 (이 수 치 는 60000 이내 의 자연수) 가 있다 고 설명 한다.Tom 은 회사 인적자원 부서 의 주관 으로 다음 과 같은 세 가지 작업 을 할 수 있다. 1. Tom 은 회 사 를 위해 능력 치가 x 인 신 입 사원 을 모집 했다. 2. Tom 은 회 사 를 위해 능력 치가 y 인 직원 을 해고 했다. 3. Tom 은 모든 직원 의 능력 치가 높 은 순위 에서 낮은 순위 로 능력 치가 W 보다 큰 직원 의 수 를 찾 아야 한다.
입력 형식 첫 줄 두 정수 n, m 는 n 명의 직원 이 있 음 을 나타 내 고 tom 의 m 항 업무 다음 줄, n 개의 정 수 는 n 명의 직원 의 능력 치 다음 m 행 을 나타 내 며 줄 마다 두 개의 정수 a, b (1 < = b < = 60000) 가 있다.a = = 1 은 능력 치가 b 인 신 입 사원 을 채용 했다 는 뜻 a = = 2 는 능력 치가 b 인 직원 을 해고 했다 는 뜻 (능력 치가 b 인 직원 이 없 으 면 이 조작 은 무효) a = = 3 은 능력 치 > b 인 직원 의 개 수 를 밝 혀 결 과 를 출력 한다.
출력 형식 은 몇 줄 이 고 줄 마다 정 수 를 입력 하 는 모든 a = = 3 작업 의 결 과 를 표시 합 니 다.
샘플 입력 샘플 입력 1: 6, 5, 9, 6, 2, 3, 5, 1, 10, 3, 6, 2, 4, 1, 2, 5, 1, 3, 2, 4, 3, 4, 3, 3, 4, 3 샘플 출력 샘플 출력 1: 32 샘플 출력 2: 2, 3 알림 n, m < = 100000
사고: 1. 모든 직원 의 능력 치 는 60000 이내 이기 때문에 구간 [1, 60001] 을 나타 내 는 선분 트 리 2 를 구축 하고 세 번 째 유형 에 대한 조회, 즉 b + 1 에서 max 구간 의 인원 을 구하 기 위해 b + 1 이 max 보다 클 때 직접 0 을 출력 하 는 것 을 주의해 야 한다.

#include
#include
using namespace std;
const int need1=60003;
const int need2=100003;

struct fy{int a,b,le,ri,val;}t[need2*2];
struct yf{int mold,num;}c[need2];

int a[need2];
int tot=0,k,ne=-need1;

void build(int x,int y)
{
    int s=++tot;
    t[s].a=x,t[s].b=y;
    if(x==y)
    {
        t[s].val=a[x];
        return ;
    }
    t[s].le=tot+1;build(x,(x+y)/2);
    t[s].ri=tot+1;build((x+y)/2+1,y);
    t[s].val=t[t[s].le].val+t[t[s].ri].val;
}
void add_(int s)
{
     if(t[s].a<=k&&k<=t[s].b) t[s].val++;
     if(t[s].le!=0&&t[t[s].le].a<=k&&k<=t[t[s].le].b) add_(t[s].le);
     else if(t[s].ri!=0&&t[t[s].ri].a<=k&&k<=t[t[s].ri].b) add_(t[s].ri);
} 
void fire_(int s)
{
    if(t[s].a<=k&&k<=t[s].b) t[s].val--;
    if(t[s].le!=0&&t[t[s].le].a<=k&&k<=t[t[s].le].b) fire_(t[s].le);
    else if(t[s].ri!=0&&t[t[s].ri].a<=k&&k<=t[t[s].ri].b) fire_(t[s].ri);
}
int cnt(int s)
{
    if(k+1<=t[s].a&&t[s].b<=ne) return t[s].val;
    int ans=0,mid=(t[s].a+t[s].b)/2;
    if(ks].le);
    ans+=cnt(t[s].ri);
    return ans; 
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int b,i=1;i<=n;i++)
    {
        scanf("%d",&b);
        if(nene=b;
        a[b]++;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&c[i].mold,&c[i].num);
        if(c[i].num>ne&&c[i].mold==1) ne=c[i].num;
    } 
    build(1,ne);
    for(int i=1;i<=m;i++)
    {
        k=c[i].num;
        if(c[i].mold==2&&a[k])
        {
            a[k]--;
            fire_(1);
        } 
        else if(c[i].mold==1) 
        {
            a[k]++;
            add_(1);
        }
        else if(c[i].mold==3) printf("%d
",k>=ne?0:cnt(1));
    }
}