HDU 3333 & 3874 (线段树+离线询问)

两个题目都是求区间之内，不重复的数字之和，3333需要离散化处理.................

调试了一下午........说多了都是泪...........

#include <iostream>   
#include <algorithm>   
#include <cmath>   
#include <cstdio>   
#include <cstdlib>   
#include <cstring>   
#include <string>   
#include <map>   
#include <queue>   
#include <climits>//形如INT_MAX一类的   
#define MAX 51111   
#define INF 0x7FFFFFFF   
#define L(x) x<<1   
#define R(x) x<<1|1   
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂   
using namespace std;  
  
inline void RD(int &ret) {  
    char c;  
    do {  
        c = getchar();  
    } while(c < '0' || c > '9') ;  
    ret = c - '0';  
    while((c=getchar()) >= '0' && c <= '9')  
        ret = ret * 10 + ( c - '0' );  
}  
  
inline void OT(int a) {  
    if(a >= 10)OT(a / 10) ;  
    putchar(a % 10 + '0') ;  
}  
  
struct node {  
    int l,r,mid,cover;  
    __int64 sum;  
} tree[MAX*4];  
  
int n,m;  
int a[MAX],va[MAX],pos[MAX],tmp[MAX];  
__int64 ans[111111 * 2];  
  
struct Node {  
    int l,r;  
    int id;  
} qes[111111 * 2];  
  
void init() {  
    memset(va,0,sizeof(va));  
}  
int search(int l,int r,int x) {  
    int mid;  
    while(l <= r) {  
        mid = (l+r) >> 1;  
        if(pos[mid] == x) return mid;  
        else if(pos[mid] > x) r = mid -1;  
        else l = mid + 1;  
    }  
}  
  
void up(int num) {  
    tree[num].sum = tree[L(num)].sum + tree[R(num)].sum;  
}  
  
void build(int l,int r,int num) {  
    tree[num].l = l;  
    tree[num].r = r;  
    tree[num].mid = (l+r) >> 1;  
    tree[num].cover = 0;  
    tree[num].sum = 0;  
    if(l == r) {  
        tree[num].sum = va[l];  
        return ;  
    }  
    build(l,tree[num].mid,L(num));  
    build(tree[num].mid + 1,r,R(num));  
    up(num);  
}  
  
void update(int l,int x,int color) {  
    if(tree[x].l == tree[x].r) {  
        tree[x].sum += color;  
        return ;  
    }  
    if(l > tree[x].mid) update(l,R(x),color);  
    else update(l,L(x),color);  
    up(x);  
}  
  
__int64 query(int l,int r,int num) {  
    if(l == tree[num].l && tree[num].r == r) {  
        return tree[num].sum;  
    }  
    if(r <= tree[num].mid) {  
        return query(l,r,L(num));  
    } else if(l > tree[num].mid) {  
        return query(l,r,R(num));  
    } else {  
        return query(l,tree[num].mid,L(num)) + query(tree[num].mid+1,r,R(num));  
    }  
}  
  
  
bool cmp(const Node &a,const Node &b) {  
    if(a.r == b.r) return a.l < b.l;  
    return a.r < b.r;  
}  
  
bool cmp2(const int &a, const int &b) {  
    return a < b;  
}  
int main() {  
    int T;  
    cin >> T;  
    while(T --) {  
        init();  
        RD(n);  
        int t = 1;  
        for(int i=1; i<=n; i++) {  
            RD(a[i]);  
            tmp[i] = a[i];  
        }  
        sort(tmp+1,tmp+1+n,cmp2);  
        pos[1] = tmp[1];  
        for(int i=2; i<=n; i++) {  
            if(tmp[i] != tmp[i-1]) {  
                pos[++t] = tmp[i];  
            }  
        }  
        build(1,n,1);  
        RD(m);  
        for(int i=1; i<=m; i++) {  
            RD(qes[i].l);  
            RD(qes[i].r);  
            qes[i].id = i;  
        }  
        sort(qes+1,qes+1+m,cmp);  
        int order = 1;  
        for(int i=1; i<=m; i++) {  
            while(qes[i].r >= order) {  
                int id = search(1,t,a[order]);  
                int ps = va[id];  
                if( ps != 0) update(ps,1,-a[order]);  
                va[id] = order;  
                update(va[id],1,a[order]);  
                order ++;  
            }  
            ans[qes[i].id] = query(qes[i].l,qes[i].r,1);  
        }  
        for(int i=1; i<=m; i++) {  
            printf("%I64d\n",ans[i]);  
        }  
    }  
    return 0;  
}  

补充：软件开发 , C++ ,

上一个：hdu 4612 Warm up
下一个：用两个队列实现栈