文档章节

【codevs 1080】线段树练习 之 花样解法

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:57
字数 1518
阅读 3
收藏 0

线段树模板题

先上暴力

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 100000 + 5;
int num[MAXN];
int n,m,q,a,b;
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
        scanf("%d",&num[i]);
    for(int i = 1;i <= n;i ++)
        num[i] += num[i - 1];
    scanf("%d",&m);
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d %d %d",&q,&a,&b);
        if(q == 1)
            for(int i = a;i <= n;i ++)
                num[i] += b;
        else
            printf("%d\n",num[b] - num[a - 1]);
    }
    return 0;
}

好了刚才的不算(虽然能AC)……

咳咳……
那么最开始的就是线段树咯~

#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
int num[200010];
struct dc{
    int l,r;
    ll sum,add;
}tree[200010*4];

void build(int p,int l,int r)
{
    tree[p].l=l,tree[p].r=r;
    if(l==r)
    {
        tree[p].sum=num[l];
        return ;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}

void spread(int p)
{
    if(tree[p].add)
    {
        tree[p*2].sum+=tree[p].add*(tree[p*2].r-tree[p*2].l+1);
        tree[p*2+1].sum+=tree[p].add*(tree[p*2+1].r-tree[p*2+1].l+1);
        tree[p*2].add+=tree[p].add;
        tree[p*2+1].add+=tree[p].add;
        tree[p].add=0;
    }
}

void change(int p,int a,int x)
{
    if(a==tree[p].l&&tree[p].r==a)
    {
        tree[p].sum+=x;
        tree[p].add+=x;
        return;
    }
    spread(p);
    int mid=(tree[p].l+tree[p].r)/2;
    if(a<=mid) change(p*2,a,x);
    if(mid<a) change(p*2+1,a,x);
    tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}

ll ask(int p,int l,int r)
{
    if(l<=tree[p].l&&tree[p].r<=r)
    {
        return tree[p].sum;
    }
    spread(p);
    int mid=(tree[p].l+tree[p].r)/2;
    ll ans=0;
    if(l<=mid) ans+=ask(p*2,l,r);
    if(mid<r) ans+=ask(p*2+1,l,r);
    return ans;
}
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&num[i]);
    build(1,1,n);
    int S;scanf("%d",&S);
    while(S--)
    {
        int s;scanf("%d",&s);
        int a,b,x;
        if(s==1)
        {
            scanf("%d%d",&a,&x);
            change(1,a,x);
        }
        else
        {
            scanf("%d%d",&a,&b);
            printf("%lld\n",ask(1,a,b));

        }
    }
    return 0;
}

恩恩,这就是线段树

然后第二个的话……显然就是好兄弟BIT了……

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 100000 + 5;
int n,z,a,b,tree[MAXN];
int lowbit(int x)
{
    return x & (- x);
}
void add(int x,int y)
{
    while(x <= n)
    {
        tree[x] += y;
        x += lowbit(x);
    }
    return;
}
int qzh(int x)
{
    int ans = 0;
    while(x > 0)
    {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}
int answer(int s,int t)
{
    return qzh(t) - qzh(s - 1);
}
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&z);
        add(i,z);
    }
    int m;
    scanf("%d",&m);
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d",&z);
        if(z == 1)
        {
            scanf("%d %d",&a,&b);
            add(a,b);
        }
        else
        {
            scanf("%d %d",&a,&b);
            printf("%d\n",answer(a,b));
        }
    }
    return 0;
}

恩恩,这就是个BIT

然后,我最喜欢的,zkw线段树!

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int MAXN = 1000000 + 5;
const int MAXM = 10000 + 5;
int treee[MAXN],M;
void init(int n)
{
    M = 1 << ((int)log2(n + 1) + 1);
    for(int i = M + 1; i <= M + n; i++)
        cin >> treee[i];
    for(int i = M - 1; i >= 1; i--)
        treee[i] = treee[i << 1] + treee[i << 1 | 1];

}
void add(int x,int a)
{
    for(treee[x += M] += a,x >>= 1;x;x >>= 1)
    {
         treee[x] = treee[x << 1] + treee[x << 1 | 1];
    }
    return;
}
int answer(int s,int t)
{
    int ans = 0;
    for(s = s + M - 1,t = t + M + 1;s ^ t ^ 1;s >>= 1,t >>= 1)
    {
        if(~s & 1) ans += treee[s ^ 1];
        if(t & 1) ans += treee[t ^ 1];
    }
    return ans;
}
int n,m,q,a,b;
int main()
{
    cin >> n;
    init(n);
    cin >> m;
    for(int i = 1;i <= m;i ++)
    {
        cin >> q >> a >> b;
        if(q == 1)
        {
            add(a,b);
        }
        if(q == 2)
        {
            cout << answer(a,b) << endl;
        }
    }
    return 0;
}

zkw太强大了……

然后……然后……也就是今天的重头戏
splay

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100000 + 5;
struct tr
{
    tr *ch[2],*f;
    int val,sz,cnt;
    bool dir()
    {
        return f -> ch[1] == this;
    }
    void maintain()
    {
        cnt = ch[0] -> cnt + ch[1] -> cnt + val;
        sz = ch[0] -> sz + ch[1] -> sz + 1;
    }
    void setc(tr *x,int v)
    {
        (ch[v] = x) -> f = this;
    }
}tree[MAXN],*root,*null;
int tot;
tr* newdot(int v,tr *f)
{
    tr *p = tree + tot++;
    p -> val = p -> cnt = v;
    p -> sz = 1;
    p -> ch[0] = p -> ch[1] = null;
    p -> f = f;
    return p;
}
void init()
{
    tot = 0;
    null = newdot(0,null);
    null -> sz = 0;
    root = null;
    return;
}
void rot(tr *x)
{
    tr *p = x -> f;
    int d = x -> dir();
    p -> f -> setc(x,p -> dir());
    p -> setc(x -> ch[d ^ 1],d);
    p -> maintain();
    x -> setc(p,d ^ 1);
    if(root == p)
        root = x;
    return;
}
void splay(tr *x,tr *to = null)
{
    while(x -> f != to)
        if(x -> f -> f == to)
            rot(x);
        else
            x -> dir() == x -> f -> dir() ? (rot(x -> f),rot(x)) : (rot(x),rot(x));
    return;
}
void add(int p,int v)
{
    tr *x = root;
    while(true)
    {
        x -> cnt += v;
        if(x -> ch[0] -> sz + 1 == p)
        {
            x -> val += v;
            break;
        }
        int d = x -> ch[0] -> sz + 1 <= p;
        if(d)
            p -= x -> ch[0] -> sz + 1;
        x = x -> ch[d];
    }
    splay(x);
    return;
}
int sum(int xx,int yy)
{
    int p = xx - 1;
    tr *x = root;
    while(true)
    {
        int d = x -> ch[0] -> sz + 1 <= p;
        if(x -> ch[0] -> sz + 1 == p)
            break;
        if(d)
            p -= x -> ch[0] -> sz + 1;
        x = x -> ch[d];
    }
    splay(x);
    p = yy + 1;
    while(true)
    {
        int d = x -> ch[0] -> sz + 1 <= p;
        if(x -> ch[0] -> sz + 1 == p)
            break;
        if(d)
            p -= x -> ch[0] -> sz + 1;
        x = x -> ch[d];
    }
    splay(x,root);
    return x -> ch[0] -> cnt;
}
int num[MAXN];
void build(int l,int r,tr * &x,tr *f)
{
    if(l > r)return;
    int mid = (l + r) >> 1;
    x = newdot(num[mid],f);
    build(l,mid - 1,x -> ch[0],x);
    build(mid + 1,r,x -> ch[1],x);
    x -> maintain();
    return;
}
int n,m,q,a,b;
int main()
{
    init();
    scanf("%d",&n);
    for(int i = 2;i <= n + 1;i ++)
        scanf("%d",&num[i]);
    build(1,n + 2,root,null);
    scanf("%d",&m);
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d %d %d",&q,&a,&b);
        if(q == 1)
            add(a + 1,b);
        else
            printf("%d\n",sum(a + 1,b + 1));
    }
    return 0;
}

恩恩,这就是棵splay……

作为后来的补充,来个分块
关于分块,调教了半小时后的经验是

  1. 编号从0开始
  2. 别忘了判断出界
  3. 任何时间要保证l < r
  4. sqrt……

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define KILL puts("haha")
using namespace std;

const int MAXN = 100000 + 5;
int sum[MAXN],num[MAXN];
int n,m;
int M;
void init()
{
    M = sqrt(n) + 1;
    for(int i = 0;i < n;i ++)
        if(i % M == 0)
            sum[i / M] = num[i];
        else
            sum[i / M] += num[i];
    return;
}
void change(int x,int y)
{
    num[x] += y;
    sum[x / M] += y;
    return;
}
int sumer(int x,int y)
{
    int ans = 0;
    while(x % M && x < y)//就是这里的这句
        ans += num[x++];
    while(y % M && y > x)
        ans += num[y--];
    ans += num[y];//别忘了闭区间……
    while(x < y)
        ans += sum[x / M],x += M;
    return ans;
}
int q,a,b;
int main()
{
    scanf("%d",&n);
    for(int i = 0;i < n;i ++)
        scanf("%d",&num[i]);
    init();
    scanf("%d",&m);
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d %d %d",&q,&a,&b);
        if(q == 1)
            change(a-1,b);
        else
            printf("%d\n",sumer(a-1,b-1));
    }
    return 0;
}

总而言之就是这样了
一个模板题也没啥可说的……

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
算法进阶路径

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Fl...

暖冰
2016/04/02
159
1
一个搞ACM需要掌握的算法

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段:练经典常用...

long0404
2015/06/24
0
0
学习算法之路(转)

路漫漫其修远兮,吾将上下而求索。。。 ======================================================== 转一个搞ACM需要的掌握的算法. 要注意,ACM的竞赛性强,因此自己应该和自己的实际应用联系起...

长平狐
2013/01/06
190
0
信息学学习笔记(1):可怕的图论

到了2019年3月份,我学算法已整一年。这个时候我觉得应该看一下提高组的复赛题了。NOIP 2018提高组初赛的题去年看过,比普及组难了不少,但是整体还好,没达到非常难的程度。复赛题我没做过,...

海天一树X
05/01
0
0
splay的各种操作与简易讲解

基本操作 插入 和二叉查找树一样,但是插入完成后要splay一下(即伸展),伸展操作下面有 伸展 查找前驱或后驱 例题:codevs1285/洛谷P2286/bzoj1208 宠物收养所 删除和合并 先把要删除的点s...

litble
2017/07/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

java快递电子面单打印接口对接demo

之前的后天管理系统的电子面单打印使用的是灵通打单。 使用相对比较麻烦,需要到处Excel之后再导入,麻烦。 快递鸟有电子面单api,后台系统直接对接很是方便,不过也遇到了好些问题。 不难是...

程序的小猿
20分钟前
3
0
fasjtjson文档

https://github.com/alibaba/fastjson/wiki/JSONField

jirak
20分钟前
3
0
Mybatis中插入多条记录

Oracle数据库 实现方法 <insert id="saveWithdrawLog"> INSERT ALL INTO OSM_TRADE_DETAIL(SID,MBR_ID,USR_ID,TRADE_MONEY,TRADE_TYPE,TRADE_TIME,TRADE_WAY,PAY_ID) VALUES(#{si......

豫华商
21分钟前
3
0
Flink on YARN(下):常见问题与排查思路

作者:杨弢(搏远) Flink 支持 Standalone 独立部署和 YARN、Kubernetes、Mesos 等集群部署模式,其中 YARN 集群部署模式在国内的应用越来越广泛。Flink 社区将推出 Flink on YARN 应用解读...

开源中国小二
23分钟前
3
0
技术沙龙|京东云端到端多媒体关键技术揭秘

编者按:从带来更高编码效率、更好的用户体验的京享高清,到直播架构与网络演进优化,从而为用户带来更流畅的观看体验,以及运维系统的异常自动修复和高弹性的多媒体存储架构,一层一层展示出...

京东云技术新知
23分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部