单点修改，区间查询 hdu1754

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 533333;
int tree[maxn], M;
inline void build (int x)
{
    for (M = 1; M <= x+1; M <<= 1);
    for (int i = M+1; i <= M+x; i++)
        scanf("%d", &tree[i]);
    for (int i = M-1; i; i--)
        tree[i] = max(tree[i<<1], tree[i<<1|1]);
}
inline void change(int x, int y)
{
    for (tree[x+=M] = y, x >>= 1; x; x >>= 1)
        tree[x] = max(tree[x<<1], tree[x<<1|1]);
}
inline int ask(int s, int t)
{
    int ans = 0;
    for (s += M-1, t += M+1; s^t^1; s >>= 1, t >>= 1)
    {
        if (~s&1)
            ans = max(ans, tree[s^1]);
        if (t&1)
            ans = max(ans, tree[t^1]);
    }
    return ans;
}
int main()
{
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF)
    {
        build (n);
        int a, b;
        char c;
        for (int i = 1; i <= m; i++)
        {
            c = getchar();
            while (c != 'Q' && c != 'U')
                c = getchar();
            scanf("%d%d", &a, &b);
            if (c == 'Q')
                printf("%d\n", ask(a, b));
            if (c == 'U')
                change(a, b);
        }
    }
    return 0;
}

区间修改，区间查询 poj3468

#include<iostream>
using namespace std;
char temp;
int n,q,m=1,cnt[262144],x,y,z;
long long t[262144],mark[262144];
long long query(int z,int y)
{
    int zn=0,yn=0;
    long long ans=0;
    z=z+m-1,y=y+m+1;
    while (z^y^1)
    {
        if (~z&1) ans+=t[z^1],zn+=cnt[z^1];
        if ( y&1) ans+=t[y^1],yn+=cnt[y^1];
        z>>=1,y>>=1;
        ans+=zn*mark[z]+yn*mark[y];
    }
    zn+=yn;z>>=1;
    while (z) ans+=zn*mark[z],z>>=1;
    return ans;
}
void add(int z,int y,long long x)
{
    z=z+m-1,y=y+m+1;
    while (z^y^1)
    {
        if (~z&1) mark[z^1]+=x,t[z^1]+=cnt[z^1]*x;
        if ( y&1) mark[y^1]+=x,t[y^1]+=cnt[y^1]*x;
        z>>=1,y>>=1;
        t[z]=t[z<<1]+t[z<<1|1]+mark[z]*cnt[z];
        t[y]=t[y<<1]+t[y<<1|1]+mark[y]*cnt[y];
    }
    z>>=1;
    while (z) t[z]=t[z<<1]+t[z<<1|1]+mark[z]*cnt[z],z>>=1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    while (m<n+2)
        m<<=1;
    for (int i=1+m;i<=m+n;i++)
        cin>>t[i], cnt[i]=1;
    for (int i=m-1;i;i--)
        t[i] = t[i<<1] + t[i<<1|1], cnt[i] = cnt[i<<1] + cnt[i<<1|1];
    while (q--)
    {
        cin>>temp;
        if (temp=='Q')
            cin>>z>>y, cout<<query(z,y)<<endl;
        else
            cin>>z>>y>>x, add(z,y,x);
    }
    return 0;
}

区间赋值 poj2528

#include<map>
#include<cstring>
#include<iostream>
using namespace std;
int a[10010],b[10010],vis[10010],now,m;
map<int,int> ha;
map<int,int>::iterator it;
int t[65536];
void add(int z,int y,int num)
{
    for (z=z+m-1,y=y+1+m;z^y^1;z>>=1,y>>=1)
    {
        if (~z&1) t[z^1]=num;
        if ( y&1) t[y^1]=num;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int cas; cin>>cas;
    while (cas--)
    {
        int q;
        cin>>q;
        ha.clear();
        now=0;
        m=1;
        for (int i=1;i<=q;i++)
            cin>>a[i]>>b[i], ha[a[i]] = ha[b[i]] = 1;
        for (it=ha.begin();it!=ha.end();it++)
            it->second=++now;
        memset(t,0,sizeof(t));
        memset(vis,0,sizeof(vis));
        while (m<now+2)
            m<<=1;
        for (int i=1;i<=q;i++)
            add(ha[a[i]],ha[b[i]],i);
        for (int i=1;i<m;i++)
        {
            t[i<<1] = max(t[i],t[i<<1]);
            t[i<<1|1] = max(t[i],t[i<<1|1]);
        }
        int ans=0;
        for (int i=1;i<=now;i++)
            if (t[i+m] && vis[t[i+m]]==0)
                ans++, vis[t[i+m]] = 1;
        cout << ans << endl;
    }
    return 0;
}