首页 » 需要再看 » 正文

Yang yang’s segment tree

Yang yang’s segment tree

来源:http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2194

Problem description

| Herowei is busy with his paper these days. In order to complete a high-quality paper, he should reference so many literature. References to the literature have good or bad influence on his paper. Let’s make it simply. Consider the page number of his paper is n, The initial quality value of each page is 0. There are m literature he can reference, each of which has good or bad influence on the page from l to r of his paper. let’s define the influence value x . Every time a reference to the literature will impact the quality of some pages. The overall effect of each page is the all influence on it. For each page, the negative quality value means this page should be modified. There q times he makes reference to the literature, he just want to know when he has made some reference to the literature. How many pages should be modified.

Input

There are multiple test cases. Each test case contains three postive integers (n,m,q) separated by a space in one line. The next m lines give the description of the reference, described as (l, r, x). Then next q lines, each contains three integers w,L,R, means when you make reference to literature w, you must consider all the all references so far and tell herowei how many pages should be modified between page L and page R. The input will be terminated by the end of input file. 1<=n,m,q<=20,000 ,1<=l<=r<=n., 1<=w<=m, -10^4<=x<=10^4.

Output

Print a line of q numbers indicates the pages should be modified.

Sample Input

4 4 2 1 4 -84 1 2 85 1 2 31 1 2 -38 1 1 4 2 1 3

Sample Output

4 1

Problem Source

2014哈尔滨理工大学秋季训练赛

反思

将区间离散为点,点的x值为left,value为以该left开始的区间的值,初始化先将一个1-n的区间和n+1~无穷大的区间放到vector中。
1. 修改操作:找到第一个小于操作left的点,从该点开始,一直算到right,如果要修改的区间是一个已有区间的子区间,则将原来的区间切开,分成几个小区间,只需新添节点即可。然后对于区间值的改变只需要改变节点的值。
2. 查询操作:同样找到第一个小于left的点,从该点开始,一直算到right,如果要查询的区间完全覆盖该区间且该区间value小于0,则加上该区间的大小。如果是该区间的子区间则加上一部分。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include<vector>
using namespace std;
inline bool scan_d(int &ret){
    char c;  int sgn;  
    if(c = getchar(), c == EOF) return 0; 
    while(c != '-' && (c<'0' || c > '9')) c=getchar();  
    sgn = (c=='-')?-1:1;  
    ret=(c=='-')?0:(c-'0');  
    while(c=getchar(), c>='0' && c<='9') ret = ret*10 + (c-'0');  
    ret *= sgn; 
    return ret;  
}
inline void out(int x){
    if(x>9)out(x/10);  
    putchar(x%10+'0');  
}
const int MAXN = 22000;
const int INF = 0x3f7f7f7f;  
struct Node{
    int x,value;
    Node(){};
    Node(int x, int value):x(x),value(value){}
    bool operator < (const Node &b)const {
        return x < b.x;
    }
    bool operator == (const Node &b)const {
        return x == b.x;
    }
};
vector<Node> vec(MAXN*2);
struct caozuo{
    int left,right,val;
}caozuo[MAXN];

int main(){
   // freopen("1.txt", "r", stdin);
   // freopen("1o.txt", "w", stdout);
    int n,m,k;
    while(scanf("%d", &n) != EOF){
        scan_d(m);  
        scan_d(k);  
        vec.clear();
        vec.push_back(Node(1,0));
        vec.push_back(Node(n+1,0));
        for(int i=1;i<=m;i++){
            scan_d(caozuo[i].left);  scan_d(caozuo[i].right);  scan_d(caozuo[i].val);  
        }
        for(int i=1;i<=k; i++){
            int op;
            scan_d(op);
            int left=caozuo[op].left,right=caozuo[op].right,val=caozuo[op].val;
            vector<Node>::iterator it = upper_bound(vec.begin(), vec.end(), Node(left,0)),it1;
            it--;  
            while((*it).x <= right){
                it1=it+1;
                int second=(*it1).x;
                if((*it).x < left){
                    if((*(it1)).x > right+1){ 
                        vec.insert(it1,Node(left,(*it).value));
                        (*it1).value += val;
                        it1++;
                        vec.insert(it1,Node(right+1,(*it).value));
                        it=it1+1;  
                    }
                    else {
                        vec.insert(it1,Node(left,(*it).value));
                        (*it1).value += val;
                        it=it1+1;  
                    }
                }
                else {

                    if(second > right+1){
                        vec.insert(it1,Node(right+1,(*it).value));
                        (*it).value += val;
                        it=it1+1;  
                    }
                    else {
                        (*it).value += val;
                        it=it1;  
                    }
                } 
            }
            scan_d(left),scan_d(right);  
            it = upper_bound(vec.begin(), vec.end(), Node(left,0));
            it--;  
            int ans=0;
            while((*it).x <= right){
                it1=it+1;
                if((*it).value >= 0){
                    it++;
                    continue;
                }
                if(right < (*it1).x){
                    ans += right-max(left, (*it).x)+1;
                }
                else {
                    ans += (*it1).x - max(left, (*it).x);
                }
                it++;
            }
            out(ans);  
            if(i == k)putchar('\n');  
            else putchar(' ');  
        }
    }
}

题解的是

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
#define oo 2000000000
#define N 40010
int a[N],b[N],add[N];
int l[N],r[N],x[N];
int w,L,R;
int n,m,q;
int sqt;
void push_down(int seg)
{
    if (add[seg])
    {
        for (int i=seg*sqt;i<(seg+1)*sqt;i++)
        {
            a[i]+=add[seg];
            b[i]+=add[seg];
        }
        add[seg]=0;
    }
}
int binary_search(int seg)//通过寻找大于等于-add[seg]的最小元素的下标,得到这一段中更新之后小于0的元素个数。
{
    int l=seg*sqt;
    int r=(seg+1)*sqt-1;
    while (l<=r)
    {
        int mid=(l+r)/2;
        if (b[mid]<-add[seg])l=mid+1;
        else r=mid-1;
    }
    return l-seg*sqt;
}
void update()
{
    int lseg=l[w]/sqt;
    int rseg=r[w]/sqt;
    if (lseg==rseg)
    {
        push_down(lseg);
        for (int i=l[w];i<=r[w];i++)a[i]+=x[w];
        for (int i=lseg*sqt;i<(lseg+1)*sqt;i++)b[i]=a[i];
        sort(b+lseg*sqt,b+(lseg+1)*sqt);
        return ;
    }
    //更新每一段
    for (int i=lseg+1;i<rseg;i++)add[i]+=x[w];

    //更新左端点所在段
    push_down(lseg);
    for (int i=l[w];i<(lseg+1)*sqt;i++)a[i]+=x[w];
    for (int i=lseg*sqt;i<(lseg+1)*sqt;i++)b[i]=a[i];
    sort(b+lseg*sqt,b+(lseg+1)*sqt);

    //更新右端点所在段
    push_down(rseg);
    for (int i=rseg*sqt;i<=r[w];i++)a[i]+=x[w];
    for (int i=rseg*sqt;i<(rseg+1)*sqt;i++)b[i]=a[i];
    sort(b+rseg*sqt,b+(rseg+1)*sqt);
}

int query()
{
    int lseg=L/sqt;
    int rseg=R/sqt;
    int ans=0;
    if (lseg==rseg)
    {
        push_down(lseg);
        for (int i=L;i<=R;i++)
            if (a[i]<0)ans++;
        return ans;
    }
    for (int i=lseg+1;i<rseg;i++)
    {
        ans+=binary_search(i);
        //printf("ans=%d\n",ans);
    }
    push_down(lseg);
    for (int i=L;i<(lseg+1)*sqt;i++)
        if (a[i]<0)
            ans++;
    push_down(rseg);
    for (int i=rseg*sqt;i<=R;i++)
        if (a[i]<0)
            ans++;
    return ans;
}
int main()
{
    //freopen("b.in","r",stdin);
    //freopen("bb.out","w",stdout);
    while (scanf("%d %d %d",&n,&m,&q)!=EOF)
    {
        for (int i=0;i<n;i++)
            b[i]=a[i]=0;
        sqt=(int)sqrt(n*1.0);
        if (sqt*sqt<n)
        {
            sqt++;
            for (int i=n;i<sqt*sqt;i++)
                b[i]=a[i]=oo;
            n=sqt*sqt;
        }
        for (int i=0;i<sqt;i++)add[i]=0;
        for (int i=1;i<=m;i++)
        {
            scanf("%d %d %d",&l[i],&r[i],&x[i]);
            l[i]--;
            r[i]--;
        }
        for (int i=0;i<q;i++)
        {
            scanf("%d %d %d",&w,&L,&R);
            L--;
            R--;
            update();
            printf("%d",query());
            if (i!=q-1)printf(" ");
            else
            printf("\n");
        }
    }
    return 0;
}
赞 (0)

发表评论

+ 85 = 93