精华内容
下载资源
问答
  • 线段树单点更新模板
    2017-02-26 15:06:40
    这份模板大概可以做到单点更新值和区间求和
    const int maxn = 50005;
    
    struct node{
        int l,r,sum;
    }tree[maxn*9];
    
    int a[maxn];
    
    void build(int l,int r,int index){
        tree[index].l = l;
        tree[index].r = r;
        if(l == r){
            tree[index].sum = a[l];
            return;
        }
        int middle = (l+r)/2;
        build(l,middle,2*index);
        build(middle+1,r,2*index+1);
        tree[index].sum = tree[2*index].sum + tree[2*index+1].sum;
    }
    
    void update(int number,int index,int ans){
        tree[index].sum += ans;
        if(tree[index].l == tree[index].r&&tree[index].l == number)
            return ;
        int middle = (tree[index].l+tree[index].r)/2;
        if(middle >= number) update(number,2*index,ans);
        else update(number,2*index+1,ans);
    }
    
    int getsum(int l,int r,int index){
        if(tree[index].l == l&&tree[index].r == r)
            return tree[index].sum;
        int middle = (tree[index].l+tree[index].r)/2;
        if(middle < l) return getsum(l,r,2*index+1);
        else if(middle >= r) return getsum(l,r,2*index);
        else return getsum(l,middle,2*index)+getsum(middle+1,r,2*index+1);
    }

    更多相关内容
  • 题意:给出n个数,m个询问,问你[l,r]区间内是否为1到r-... 考虑线段树做法,我们记录每个的靠左最近的相同元素的位置,然后求 整个区间的最大值(即最大的前驱)如果小于l,即满足条件,输出YES。 好吧,其实这个题

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5172

    题意:给出n个数,m个询问,问你[l,r]区间内是否为1到r-l+1的全排列。 大小很容易我们通过记录前缀和很容易求出来,但是关键是去重。 考虑线段树做法,我们记录每个点的靠左最近的相同元素的位置,然后求 整个区间的最大值(即最大的前驱)如果小于l,即满足条件,输出YES。

    好吧,其实这个题目我是搜的RMQ算法出来的,因为我想练一下RMQ算法,所以我就看了一下别人的博客,自己也写了一下,结果死活MLE。。。

    好吧,我仔细看了一下,1000000的数据量用RMQ开一个二维数组1000000*20,显然会超内存。。。

    结果我不得不老老实实的滚回去用线段树写了。。。orz....

    RMQ的MLE代码:

    #include<iostream>
    #include<string>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    #include<map>
    #include<cmath>
    #include<stack>
    #include<set>
    #include<vector>
    #include<algorithm>
    #define LL long long
    #define inf 1<<30
    #define sf(a) scanf("%d",&a);
    #define CLEAR(a,b) memset(a,b,sizeof(a))
    using namespace std;
    /*
        TLE...显然超内存;
    */
    const int N=1000005;
    int n,m,a,b;
    int num[N],pre[N];
    int dp[N][21];
    int sum[N];
    void ST(int len)
    {
        for(int i=1;i<=n;i++) dp[i][0]=num[i];
        for(int j=1;1<<j < n;j++){
            for(int i=1;i+(1<<j)-1<n;i++){
                dp[i][j]=max(dp[i][j-1],dp[i+1<<(j-1)][j-1]);
            }
        }
    }
    int rmq(int s,int v)
    {
        int k=(int)(log(v-s+1)*1.0/log(2.0));
        return max(dp[s][k],dp[v-1<<k+1][k]);
    }
    int main()
    {
        while(~scanf("%d%d",&n,&m)){
            CLEAR(pre,0);
            CLEAR(sum,0);
            for(int i=1;i<=n;i++){
                sf(a);
                sum[i]+=sum[i-1]+a;
                num[i]=pre[a];
                pre[a]=i;
            }
            ST(n);
            while(m--){
                sf(a);sf(b);
                double tmp=(b-a+2)*(b-a+1)*1.0/2.0;
                if(tmp!=sum[b]-sum[a-1]){
                    //cout<<tmp<<' '<<sum[b]-sum[a-1]<<' ';
                    printf("NO\n");
                    continue;
                }else{
                    if(rmq(a,b)<a) printf("YES\n");
                    else printf("NO\n");
                }
            }
        }
        return 0;
    }
    
    

     

    线段树AC代码:

    #include<iostream>
    #include<string>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    #include<map>
    #include<cmath>
    #include<stack>
    #include<set>
    #include<vector>
    #include<algorithm>
    #define LL long long
    #define inf 1<<30
    #define s(a) scanf("%d",&a)
    #define CLEAR(a,b) memset(a,b,sizeof(a))
    using namespace std;
    const int N=1000005;
    int n,m,a,b;
    int pre[N],sum[N];  //  sum存总和,pre定位该数字上一次出现的位置;
    struct node
    {
        int l,r;
        int pre;    //  用线段树维护最近一个重复的数字;
    }node[N<<2];
    void PushUp(int rt)
    {
        node[rt].pre=max(node[rt<<1].pre,node[rt<<1|1].pre);
    }
    void build(int l,int r,int rt)
    {
        node[rt].l=l;
        node[rt].r=r;
        node[rt].pre=0;
        if(l!=r){
            int mid=(l+r)>>1;
            build(l,mid,rt<<1);
            build(mid+1,r,rt<<1|1);
        }
    }
    void Insert(int v,int p,int rt)
    {
        int ll=node[rt].l,rr=node[rt].r;
        if(ll==rr&&p==ll){
            node[rt].pre=pre[v];
            return;
        }
        int mid=(ll+rr)>>1;
        if(p<=mid) Insert(v,p,rt<<1);
        else Insert(v,p,rt<<1|1);
        PushUp(rt);
    }
    int query(int l,int r,int rt)
    {
        int ll=node[rt].l,rr=node[rt].r;
        if(ll==l&&rr==r){
            return node[rt].pre;
        }
        int mid=(ll+rr)>>1;
        if(r<=mid) return query(l,r,rt<<1);
        else if(l>mid) return query(l,r,rt<<1|1);
        else return max(query(l,mid,rt<<1),query(mid+1,r,rt<<1|1));
    }
    int main()
    {
        while(~s(n)){
            s(m);
            CLEAR(pre,0);
            CLEAR(sum,0);
            build(1,n,1);
            for(int i=1;i<=n;i++){
                s(a);
                sum[i]+=sum[i-1]+a;
                Insert(a,i,1);
                pre[a]=i;
            }
            while(m--){
                s(a);s(b);
                int tmp=(b-a+2)*(b-a+1)*1.0/2.0;    //  如果是全排列那么最后的和必然符合这个公式;
                if(sum[b]-sum[a-1]!=tmp){
                    printf("NO\n");
                    continue;
                }else{
                    if(query(a,b,1)<a) printf("YES\n"); //  查询该区间最近一个重复的数字出现的位置,如果比a小,那就说明这个区间没有出现过重复的数字;
                    else printf("NO\n");
                }
            }
        }
        return 0;
    }
    


     

    展开全文
  • //CodeForces 91B Queue 线段树 单点更新 成段查询 /* 题目地址:http://codeforces.com/problemset/problem/91/B 题意: 有n个数的失望值, 失望值的定义是:离它最远的比它小的数 与 它本身之间 间隔的数的数量 ...
    //CodeForces 91B Queue 线段树 单点更新 成段查询
    /*
    题目地址:http://codeforces.com/problemset/problem/91/B
    
    题意:
    有n个数的失望值,
    失望值的定义是:离它最远的比它小的数 与 它本身之间 间隔的数的数量
    
    思路:
    线段树,结点保存区间最小值
    每次将当前的数更新为INF,然后查找整个区间内最右边的比它小的数的下标
    
    */
    
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    #define INF 1000000005
    #define N 100005
    #define lson rt<<1,l,mid
    #define rson rt<<1|1,mid+1,r
    
    int mmin[N<<2],s[N];
    
    int Min(int x,int y){
    	return x<y?x:y;
    }
    
    void Pushup(int rt){
    	mmin[rt] = Min(mmin[rt<<1],mmin[rt<<1|1]);
    }
    
    void Build(int rt,int l,int r){
    	if(l == r){
    		scanf("%d",&mmin[rt]);
    		s[l] = mmin[rt];
    		return ;
    	}
    	int mid = (l + r) >> 1;
    	Build(lson);
    	Build(rson);
    	Pushup(rt);
    }
    
    void Update(int rt,int l,int r,int x){
    	if(l == r){
    		mmin[rt] = INF;
    		return ;
    	}
    	int mid = (l + r) >> 1;
    	if(x <= mid) Update(lson,x);
    	else		 Update(rson,x);
    	Pushup(rt);
    }
    
    int Query(int rt,int l,int r,int x){
    	if(l == r)
    		return l;
    	int mid = (l + r) >> 1;
    	if(mmin[rt<<1|1] < x) return Query(rson,x);
    	else			  return Query(lson,x);
    }
    
    int main(){
    	int n,i;
    	while(scanf("%d",&n)!=EOF){
    		Build(1,1,n);
    		for(i = 1; i <= n; ++i){
    			Update(1,1,n,i);
    
    			if(mmin[1] >= s[i])
    				printf("%d%c",-1,i==n?'\n':' ');
    			else
    				printf("%d%c",Query(1,1,n,s[i])-i-1,i==n?'\n':' ');
    		}
    	}
    	return 0;
    }

    展开全文
  • 单点更新线段树

    2017-02-02 14:17:50
    线段树是一种强(傻)大(逼)的数据结构,但博主实在是无聊,只好默默的玩一下这种强(傻)大(逼)的数据结构(博主N年前就已经掌握了这种数据结构)。但博主为了共产(工厂)主义事业,终于写下了这个代码(为...

    线段树是一种强(傻)大(逼)的数据结构,但博主实在是无聊,只好默默的玩一下这种强(傻)大(逼)的数据结构(博主N年前就已经掌握了这种数据结构)。但博主为了共产(工厂)主义事业,终于写下了这个代码(为NOIPPJ的水题奋斗)。

    /*************************************************************************
        > File Name: \LJF\数据结构\树\线段树\单点更新模板.cpp
        > Author: ljf_cnyali
        > Mail: ljfcnyali@gmail.com 
        > Last modifiedz: 2017-02-2 11:49
        > Description: This is a large group of God's program information.
     ************************************************************************/
    
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    #include<cmath>
    #include<queue>
    #include<map>
    #include<set>
    #include<vector>
    #include<algorithm>
    
    using namespace std;
    
    #define REP(i, a, b) for(int i = (a), _end_ = (b);i <= _end_; ++ i)
    #define mem(a) memset((a), 0, sizeof(a))
    #define str(a) strlen(a)
    #define lson l, mid, rt << 1
    #define rson mid + 1, r, rt << 1 | 1
    
    const int maxn = 10000;
    
    int n, m;
    
    int Tree[maxn << 2];
    
    void pushup(int rt) {
        Tree[rt] = Tree[rt << 1] + Tree[rt << 1 | 1];   
    }
    
    void Bulid(int l, int r, int rt) {
        if(l == r) {
            Tree[rt] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        Bulid(lson);
        Bulid(rson);
        pushup(rt);
    }
    
    void update(int pos, int val, int l, int r, int rt) {
        if(l == r) {
            Tree[rt] += val;
            return;
        }   
        int mid = (l + r) >> 1;
        if(pos <= mid)
            update(pos, val, lson);
        else
            update(pos, val, rson);
        pushup(rt);
    }
    
    int query(int L, int R, int l, int r, int rt) {
        if(L <= r && r <= R)
            return Tree[rt];
        int mid = (l + r) >> 1;
        int ret = 0;
        if(L <= mid)
            ret += query(L, R, lson);
        if(R > mid)
            ret += query(L, R, rson);
        return ret;
    }
    
    int main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    
    
        return 0;
    }
    
    
    展开全文
  • http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem_id=1472 #include &lt;iostream&gt; #include &lt;cstdio&gt; #include &lt;cstring&...#define maxn ...
  • 线段树 单点更新

    2013-11-10 01:21:40
    HDU 2795 题意:要求所贴广告在广告牌的最上面 最左边, 求每张广告对应的所在行数 #include #include using namespace std; int node[(200000) + 10];...void construct(int o, int l, int r) ...
  • B - Minimum 线段树单点更新

    千次阅读 2019-04-07 14:04:35
    线段树单点更新板子 参考板子: https://blog.csdn.net/nuoyanli/article/details/89039581 板子记得没问题,为啥超时==(就将结构体Tree改为了双数组查询就a了emmm)好吧不是结构体的锅,将比赛代码重新打...
  • struct Tree { int left, right; int max, sum; }; void update(int id, int pos, int val) { if(tree[id].left == tree[id].right) { tree[id].sum = tree[id].max = val;...int mid = (tr
  • Multiply game Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2109 Accepted Submission(s): 748 Problem Description ...Tired of playing
  • 原理就大概如图所示,线段树的每个节点都是原数组的一段区间和,而叶子节点就是原数组对应 的值 建树代码: void build(int p,int lf,int rt){//建树 ans[p]=0; if(lf==rt) { ans[p]=A[lf]; return ; } int mid...
  • 二维线段树就是在一棵线段树的每一个节点,都保存着另一棵线段树的根节点编号。注意更新操作,稍微有点复杂,给个图解。可以结合代码理解,代码在关键地方写了注释。(感谢xbb的指导) 代码: #inclu...
  • 其实线段树恰好可以解决从圈中删除一人这个问题,即单点更新。 因为n个小孩依次出圈,要知道谁的糖果最多,也就是求谁出圈的次序号的约数最多。所以我们可以预处理,先求出1~n中约数最多的那个数maxid,其约数个数...
  • Problem Description At the entrance to the university, there is a huge rectangular billboard of size h*w (h is its height and w is its width). The board is the place where all possible announcements ...
  • 线段树单点更新总结

    2017-08-31 19:56:17
    这几天看的是单点更新的博客,感觉其实也是有模板,就是初始时建立线段树,还有一个更新值的,还有查询的,其实就是从父结 点到子结点更新,无论是最大值还是求某个区间的和,都是通过父结点,子结点的作用实现。...
  • 条件:1单点更新 2 区间求和 思路:简单的线段树基本操作 扩展: 线段树:它将每个区间划分成一些简单的区间,每个区间对应线段树中的一个节点。对于线段树中每一个非叶子节点[a,b],它的左子树区间表示为[a,(a...
  • 线段树还可以维护最大连续子序列和啊。。没想到 对于这种首尾相接的数列,所求为其中一部分连续子序列的,可以分两种结果讨论(以序列a1,a2,a3,a4,a5为例): 要么在序列中间,要么在序列两头 1)所求结果子序列没有...
  • //HDOJ 3874 Necklace 线段树 单点更新 成段查询 /* 题意:求某区间没所有值不同的数的总和 思路:先对所有的询问按照区间末尾排序 然后从序列前面开始遍历,当遇到相同的元素的时候 将前面的元素删除,这样...
  • 终于把那篇博客里单点更新的题写完了,前面5道题都很简单,就是在最后一道卡的时间比较长,一是题意没明白,二是不知道反素数这个东西,不过还是看题解过掉了这题。嗯,下面该再开个区间更新什么的写了。 ...
  • CodeForces - 160E(线段树单点更新+离散)
  • 线段树单点修改

    2019-10-22 11:46:04
    https://www.luogu.org/problem/P3374 开始,我的单点修改只改变的线段树上的一个结点的值,实际上,要改变一连串的值才可以。
  • 线段树无从下手!..看了大牛的分析..大彻大悟..因为一个announcement最多占一行...而announcement的总数n  构图..每个叶子节点代表每个行所剩下能用的格子数...非叶子节点表示其孩子中格子数最多为多少...  当要...
  • 那么利用线段树单点更新即可实现维护。而查找中位数时只需要在线段树中找到第n/2大的数所在的叶子节点,叶子节点所对应的区间(叶子节点的区间l=r)值即为中位数。 AC代码: #include #include #include #...
  • POJ 2828 线段树 单点更新,单点查询

    千次阅读 2013-09-24 13:20:26
    void updata_point(int pos,int id, ll data){//单点更新 if(tree[id].l == tree[id].r) { tree[id].num--; tree[id].sum = data; return ; } tree[id].num--; if( tree[ L(id) ].num > pos)...
  • POJ.2299 Ultra-QuickSort (线段树 单点更新 区间求和 逆序对 离散化)题意分析前置技能 线段树求逆序对 离散化 线段树求逆序对已经说过了,具体方法请看这里 离散化 有些数据本身很大,自身无法作为数组的下标...
  • 好吧,写了这么多单点更新的题目,这样的就很简单了,不过我第一次用这样的风格写代码;向这种简短风格靠齐; 不过题目给的数据感觉还挺坑的,还好我机智的看了Discuss。。。。哈哈,仰天长笑。。。。 #include #...
  • 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,... 在这片文章中,我先讲一下最基本的建树,单点修改,单点/区间查询 线段树是一种用空间换时间的算法开建树的数组时切记 一定要开4倍的...
  • hdu1166敌兵布阵 树状数组&线段树 单点更新求区间和

    万次阅读 热门讨论 2017-03-13 20:17:32
    // Binary Indexed Tree二进制变址 #include #include #include using namespace std; int t[50005],n; inline int lowbit(int x){ return x&-x; } void add(int i,int tt){ //t[i] and the late of it add nt. ...
  • POJ.3321 Apple Tree ( DFS序 线段树 单点更新 区间求和)题意分析卡卡屋前有一株苹果树,每年秋天,树上长了许多苹果。卡卡很喜欢苹果。树上有N个节点,卡卡给他们编号1到N,根的编号永远是1.每个节点上最多结一个...
  • poj2481之线段树单点更新

    千次阅读 2013-05-28 09:04:32
    每次更新e,更新的目的是使得包含e的区间含有的个数+1 对于比牛[s,e]强壮的牛的个数则只要查询区间[e,MAX]内的的个数 (由于前面更新的牛s当前的牛的s,所以只要前面的牛的e>=当前的牛的e即可,即求[e,MAX]含有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,937
精华内容 12,774
关键字:

线段树单点更新