【CDOJ1059】秋實大哥與小朋友

題目連結：http://mozhu.today/#/problem/show/1059

題解：

區間更新單點查詢，裸裸的樹狀數組/線段樹

考慮到m範圍太大，是以要離散化

因為是單點修改，是以沒有涉及到的點是不需要管的

将所有修改和詢問記錄下來離線處理，離散化之後正常做就好了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int tree[N],n,m,l[N],r[N],v[N],ask[N],tot;
int a[N<<];
bool aa[N];

int lowbit(int x)
{
    return x&(-x);
}

void add(int pos,int val)
{
    for(int i=pos;i;i-=lowbit(i))
        tree[i]+=val;
}

int sum(int pos)
{
    int ret=;
    for(int i=pos;i<=tot;i+=lowbit(i))
        ret+=tree[i];
    return ret;
}

int main()
{
    int tmp,cnt=;
    scanf("%d%d",&n,&m);
    for(int i=;i<=m;i++)
    {
        scanf("%d",&tmp);
        if(tmp==)
        {
            scanf("%d%d%d",&l[i],&r[i],&v[i]);
            a[++cnt]=l[i];a[++cnt]=r[i];
            aa[i]=;
        }
        else
        {
            scanf("%d",&ask[i]);
            a[++cnt]=ask[i];
        }
    }
    sort(a+,a+cnt+);
    tot=unique(a+,a+cnt+)-a-;
    for(int i=;i<=m;i++)
    {
        if(aa[i])
        {
            l[i]=lower_bound(a+,a+tot+,l[i])-a;
            r[i]=lower_bound(a+,a+tot+,r[i])-a;
        }
        else ask[i]=lower_bound(a+,a+tot+,ask[i])-a;
    }
//  for(int i=;i<=m;i++)
//      if(aa[i]) cout<<l[i]<<" "<<r[i]<<endl;
//      else cout<<ask[i]<<endl;
    for(int i=;i<=m;i++)
    {
        if(aa[i])
        {
            add(l[i]-,-v[i]);
            add(r[i],v[i]);
        }   
        else printf("%d\n",sum(ask[i]));
    }
    return ;
}