线段树

POJ 2777 Count Color 附带线段树小结

Posted on

POJ 2777 题解

好久没这么兴奋过了
poj2777 这绝对是 是道线段树的好题 至少对我来说
一开始看这题的时候 看了一下数据范围就知道了 可以用位运算 进行状态压缩
我想要自己做 对 完全不看题解 结果问题就慢慢显现出来了
尤其是我对pushdown操作的理解完全不够 最后还是自己动笔好好画了一下模拟几遍才恍然大悟 我真是太辣鸡了

先附上 代码和注释 最后写上我对线段树基础操作的理解(包括以前写的一些 觉得太基础了就没卸载博客上 今天就在这里汇总一下

AC Code(G++好像就超了 C++能过

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#define root tree[id]
#define lson tree[id<<1]
#define rson tree[id<<1|1]

using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=100005;
int st,en,n,m,qnum;
long long change,col;//col是最后query的最终颜色汇总   最后对其位操作计算颜色数量即可
struct segtree
{
    int le,ri;
    long long color,change_color;//这段区间上的颜色总和   延迟更新标记
} tree[maxn<<2];

inline void pushup(int id)
{
    root.color=lson.color|rson.color;//颜色汇总
}

inline void pushdown(int id)
{
    if(root.change_color!=0&&root.le!=root.ri)
    {
        long long cc=root.change_color;
        lson.change_color=rson.change_color=lson.color=rson.color=cc;
        root.change_color=0;
    }
}

void build_tree(int id,int le,int ri)
{
    root.le=le,root.ri=ri,root.change_color=0;
    root.colo=1;
    if(le==ri) return;
    int mid=(le+ri)/2;
    build_tree(id<<1,le,mid);
    build_tree(id<<1|1,mid+1,ri);
}

void update(int id)
{
    int le=root.le,ri=root.ri;
    if(st<=le&&ri<=en)
    {
        root.color=root.change_color=change;
        return ;
    }
    pushdown(id);
    int mid=(le+ri)/2;
    if(st<=mid) update(id<<1);
    if(en>mid) update(id<<1|1);
    pushup(id);
}

void query(int id)
{
    int le=root.le,ri=root.ri;
    if(st<=le&&ri<=en)
    {
        col=col|root.color;
        return ;
    }
    pushdown(id);//牛逼啊!!!!真的牛逼!!!!pushdown这个位置  沃夫
    int mid=(le+ri)/2;
    if(st<=mid) query(id<<1);
    if(en>mid) query(id<<1|1);
}

int main()
{
    while(scanf("%d%d%d",&n,&m,&qnum)!=EOF)
    {
        char op[2];
        build_tree(1,1,n);
        while(qnum--)
        {
            scanf("%s",op);
            if(op[0]=='C')
            {
                scanf("%d%d%I64d",&st,&en,&change);
                if(st>en) swap(st,en);
                change=1<<(change-1);
                update(1);
            }
            else
            {
                scanf("%d%d",&st,&en);
                if(st>en) swap(st,en);
                int ans=0;
                col=0;//col初始化
                query(1);
                for(int i=0; i<m; i++)
                    if((col>>i)&1) ans++;
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}

线段树小结

下面是对线段树的理解(从小白开始的历程 不喜勿喷…………

线段树的精髓 就在于 它永远都是从根节点出发

1.关于query以及update时判断的标志 st<=le&&ri<=en 的理解
假如区间为 1-7 要求求出 2-6的值
并不是说 什么2-3 2-4 3-5 3-6 什么乱七八糟的都可以满足条件
首先由于线段树的性质 如果该节点 在区间内部 那么只要我一个return 该节点的所有叶子节点就不会再出现,更不用说是该节点内的数字
也就是说 假如我 1-4 满足条件 那么1-2 3-4都不会再出现 1,2,3,4也不会再次被访问到
所以 如此继续向下查询 线段式地返回 最后就是所要求的区间值

2.关于pushdown与pushup的理解
就如字面意思 假如 一个节点更新 那么它的叶子节点和父亲节点都需要更新
如果每次都这么向下向上更新 百分之8000要超时 效率低下
所以我们先暂时向下更新 一直向下更新 到最后再一起向上更新 如此就能实现所有更新

3.关于pushdown和lazy标记的详解

现在才知道为什么总是说线段树对递归的要求稍微高了一些

以此题为例 在update时 在此区间更新后 直接return 这个区间和他的子区间都不会被再次访问

并不是说不会更新 而是他觉得暂时没必要

当query操作时 如果你不会访问他的子区间 他就不会更新

eg 总区间是 1-12 你更新 4-5区间 查询 5-6区间

当你访问到4-5区间时 发现没有符合条件 他才会向下更新 4和5节点

这样说来可能还有优化的余地 就是当切仅当你要查询的区间与 你当前访问的区间有交集的时候 才向下更新 也不失为一个方法 有兴趣的可以尝试一下

啊! 果然 算法的优化是无止尽的!!

BFS

POJ 3503 Summits

Posted on

再一次感慨英语是多么的重要 今天打比赛写到这题一直看不懂 尤其是最关键的那个双重否定一出来我整个人就懵逼了
我还是弱弱的简单说一下题意吧

题意:
就是给你一个二维数组 每个值表示高度
给你 长 宽 和一个数d
如果一个点高度为h 只走 高度大于 h-d 的点并且达不到一个更高的点 那么这个点就是一个峰值
求峰值的数目

思路 :
贪心 从最高点出发搜索 比它小的和它连通的都标记成 原点高度 既可以标记 又可以减少访问
后面访问见注释

下面附上代码和注释
第一次用了STL的队列和优先队列 结果TLE
无奈用了模拟队列试了一下就过了

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>


using namespace std;
const int maxn=505;
int row,col,d;
int mat[maxn][maxn];
int vis[maxn][maxn];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
struct node
{
    int x,y;
    int val;
}preque[maxn*maxn],que[maxn*maxn];


bool cmp(const node& a,const node& b)
{
    return a.val>b.val;
}


int bfs(int k)
{
    int front=1,rear=1;
    int ans=1;
    vis[preque[k].x][preque[k].y]=preque[k].val;
    que[front]=preque[k];
    int h=preque[k].val;
    bool flag=true;
    while(front<=rear)
    {
        node temp=que[front++];
        int x=temp.x,y=temp.y,val=temp.val;
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx<=0||x>row||y<=0||y>col) continue;//不在区域内
            if(h-mat[xx][yy]>=d) continue;//就如上述说的  高度必须小于h-d
            if(vis[xx][yy]>h)//遇到更高的
            {
                flag=false;
                continue ;
            }
            if(vis[xx][yy]==h) continue;//已访问
            if(mat[xx][yy]==h) ans++;//碰到同一高度的   如果原点是  那么这个点也满足条件
            vis[xx][yy]=h;//标记
            que[++rear].x=xx;
            que[rear].y=yy;
        }
    }
    if(flag) return ans;
    else return 0;
}




int main()
{
    int test;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d%d%d",&row,&col,&d);
        int ans=0,num=0;
        memset(vis,-1,sizeof vis);
        for(int i=1; i<=row; i++)
            for(int j=1; j<=col; j++)
            {
                scanf("%d",&mat[i][j]);
                preque[++num].x=i;
                preque[num].y=j;
                preque[num].val=mat[i][j];
            }
        sort(preque+1,preque+1+num,cmp);
        for(int i=1;i<=num;i++)
            if(vis[preque[i].x][preque[i].y]==-1)
            ans+=bfs(i);
        printf("%d\n",ans);
    }
    return 0;
}
DFS

HDU 1198 Farm Irrigation

Posted on

不太一样的搜索水题

题意:
A--K对应不同水管 要事整个田地都能灌溉到水 ,问 需要到少水源

思路:
一开始想的就是深搜 只是方向都不同罢了 和求连通区域个数没什么区别 属于最水的搜索题

AC Code

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
const int maxn=60;
char mat[maxn][maxn];
bool vis[maxn][maxn];
int row,col;
int dir[12][4]=
{
    {1,0,0,1},{1,1,0,0},{0,0,1,1},{0,1,1,0},
    {1,0,1,0},{0,1,0,1},{1,1,0,1},{1,0,1,1},
    {0,1,1,1},{1,1,1,0},{1,1,1,1}
};
int dx[]= {-1,0,1,0};
int dy[]= {0,1,0,-1};

bool judge(int x,int y)
{
    return x>0&&x<=row&&y>0&&y<=col&&!vis[x][y];
}

void dfs(int from,int x,int y)
{
    int num=mat[x][y]-'A',xx,yy;
    if(from<4)
        if(!dir[num][(from+2)%4]){vis[x][y]=false; return ;}
    for(int i=0; i<4; i++)
    {
        if(dir[num][i])
        {
            xx=x+dx[i];
            yy=y+dy[i];
            if(judge(xx,yy))
            {
                vis[xx][yy]=true;
                dfs(i,xx,yy);
            }
        }
    }
}

int main()
{
    while(scanf("%d%d",&row,&col),row>0&&col>0)
    {
        getchar();
        for(int i=1; i<=row; i++)
            scanf("%s",mat[i]+1);
        memset(vis,false,sizeof vis);
        int ans=0;
        for(int i=1; i<=row; i++)
            for(int j=1; j<=col; j++)
                if(!vis[i][j])
                {
                    ans++;
                    vis[i][j]=true;
                    dfs(maxn,i,j);
                }
        printf("%d\n",ans);
    }
    return 0;
}
最大匹配

FZU 2039 Pets

Posted on

匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。

其实说白了 这个算法用途有限 只能求二分图的最大匹配(如果没有任何扩展,毕竟我是鶸……

题目是一个人与狗的故事
这里每个人都想日狗 所以肯定是一对一的啊 但总共有 n个人 m只狗 e个先决条件
这些条件中 第ai个人不喜欢第bi只狗
问最多能让多少人 日到狗

AC Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <cmath>
#include <iostream>
#include <cstdlib>

using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1100;
int n,m,qnum;
int cus[maxn];
bool vis[maxn],g[maxn][maxn];

void init()
{
    memset(g,true,sizeof g);
    memset(cus,0,sizeof cus);
    int u,v;
    for(int i=0; i<qnum; i++)
    {
        scanf("%d%d",&u,&v);
        g[u][v]=false;
    }
}

bool fin(int a)
{
    for(int i=1; i<=m; i++)
        if(g[a][i]&&!vis[i])
        {
            vis[i]=true;
            if(cus[i]==0||fin(cus[i]))
            {
                cus[i]=a;
                return true;
            }
        }
    return false;
}

int main()
{
    int test;
    scanf("%d",&test);
    for(int t=1; t<=test; t++)
    {
        scanf("%d%d%d",&n,&m,&qnum);
        init();
        int ans=0;
        for(int i=1; i<=n; i++)
        {
            memset(vis,false,sizeof vis);
            if(fin(i)) ans++;
        }
        printf("Case %d: %d\n",t,ans);
    }
    return 0;
}
DFS

CodeForces 14D Two Paths

Posted on

一看到这道题我就是大写的懵逼
因为上半年去华科还是地大打邀请赛的时候做过类似的题目,当初是写不来的 结果现在……………………还是写不来………………造孽啊

题意:
给你一个无向不成环的图 让你找出两条不相交的树链 使其乘积最大

思路 :
枚举每一条道路 并使其暂时断裂 再从这条道路的两端开始搜索 寻找最长的树链即可
说实话 搜索的题目虽然说做的还凑合 但是这种给你一个连通方式 并以此形成无向图 再加以搜索的题目我还是第一次做
我先想得是用二维矩阵保存路径 以G[u][v] 表示从 u到v是连通的 再用vector省点空间
之后我较为习惯的用了BFS 然后就进入了无限懵逼崩溃懵逼崩溃的状态 说到底用矩阵保存如果不用上结构体的话 很难记录链长
无奈还是写了DFS

AC Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;
const int maxn=220;
bool vis[maxn];
vector<int> G[maxn];
int ans;

int dfs(int v,int x)
{
    int sum=0;
    int max1=0,max2=0;
    for(int i=0; i<G[v].size(); i++)
    {
        if(G[v][i]!=x)
        {
            sum=max(sum,dfs(G[v][i],v));//sum得到从一个NODE出发的树的直径   循环操作得到最大
                                        //与此同时 ans也在计算着从改点出发的最长树链
            if(ans>max1)
            {
                max2=max1;
                max1=ans;
            }
            else max2=ans>max2?ans:max2;
        }
    }
    sum=max(sum,max1+max2);//最后sum得到从V出发的树的直径
    ans=max1+1;//max1为该node的最长树链  因为递归返回  最大树链长度+1
    return sum;
}

int main()
{
    int n,a,b;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0; i<=n; i++) G[i].clear();
        for(int i=0; i<n-1; i++)
        {
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
            G[b].push_back(a);
        }
        int last_ans=0;
        for(int i=0; i<n; i++)
        {
            int num=G[i].size(),temp;
            for(int j=0; j<num; j++)
            {
                int ans=0;
                temp=dfs(i,G[i][j])*dfs(G[i][j],i);
                last_ans=max(last_ans,temp);
            }
        }
        printf("%d\n",last_ans);
    }
    return 0;
}
单调栈

POJ 3494 Largest Submatrix of All 1’s

Posted on

题意:
给你一个矩阵 全由0,1组成 让你找出其中由1组成的面积最大的矩形
题意非常简单 但让人无从下手
其实如果我们一行一行处理 将矩阵转换到 柱状图 就有想法了
eg

1 0 1 00 0 1 0
0 1 1 1-->0 1 2 1
1 1 0 1-->1 2 0 2
1 0 1 12 0 1 3

再对每一行进行计算连续的最大矩形面积即可

我的方法是直接把 terrible set 的方法拉过来用的 事实证明 效率还好

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>

using namespace std;

int row,col,ans,tw,temp,top;
int mat[2010][2010];

struct grid
{
    int wid,high;
    grid(int a=0,int b=1):high(a),wid(b){}
}st[2010];

void push(int h)
{
    tw=temp=0;
    while(top>0)
    {
        if(st[top].high>h)
        {
            tw+=st[top].wid;
            if((temp=tw*st[top].high)>ans)
                ans=temp;
            top--;
        }
        else break;
    }
    tw++;
    if((temp=tw*h)>ans) ans=temp;
    if(h)  st[++top]=grid(h,tw);
}

int main()
{
    while(scanf("%d%d",&row,&col)!=EOF)
    {
        for(int i=1; i<=row; i++)
            for(int j=1; j<=col; j++)
                scanf("%d",&mat[i][j]);
        for(int i=1; i<=col; i++)
            mat[0][i]=0;
        ans=0;
        for(int i=1; i<=row; i++)
        {
            top=0;
            for(int j=1; j<=col; j++)
                if(mat[i][j]) mat[i][j]+=mat[i-1][j];
            for(int j=1; j<=col; j++)
                push(mat[i][j]);
            tw=temp=0;
            while(top>0)
            {
                tw+=st[top].wid;
                if((temp=tw*st[top].high)>ans)
                    ans=temp;
                top--;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
数状数组

POJ 2299 Ultra-QuickSort

Posted on

去年第一次看到这个马桶塞 是俱乐部介绍归并排序的时候 当初也写了很久 这里就不说了

现在暑假集训 放在树状数组专题 没多久就有了想法

但是以下算法适合应对数据较小的题目 此题不适合 可看可不看

假如以我们一个人的思维求逆序数 我们会计算在它后面的 而且比它小的数字的个数sum 所以我们只要从末尾开始计算 在n位置的前n-1项的sum 就能一个不漏计算出这个位置的逆序数

以样例为例 9 1 0 5 4 先全部初始化为0

1.先计算4 前面全为0 得0

2.计算5 前面有一个4 得1

3.计算0 前面全为0 得0

4.计算1 前面有一个0 得1

5.计算9 前面有0,1 4 5 得4

所有相加的答案 6

结果就是RE了 因为 a[i]的范围是小于等于999,999,999 以上算法必须开这么大的数组 所以RE 不行

没办法 只能去看了题解 看到有指出离散化的思想 卧靠 我完全不懂 又小补了一下离散化 这里就不说了

如果要离散化上述算法 我想是应该将 9 1 0 5 4 想办法 转化成 5 2 1 4 3 但是又要排序又要还原 我就懵逼了

下面是我看的题解思路

开一个结构体记录 下标pos和数值val 以val升序排序 再开个数组 记录排序后的下标

eg

val 9 1 0 5 4-> val 0 1 4 5 9重点来了 大神题解里是按照每个点所影响产生的逆序数 和我上面不一样
pos 1 2 3 4 5 排序离散化-> pos 3 2 5 4 1核心就是 我从头开始放置每一个数 我放第i个数 那么如果是升序的话 我前面理应有i-1个数字
-> reflet 1 2 3 4 5但是因为乱序放置 产生了 i-sum(i) 个逆序数

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <stack>

using namespace std;
int n,maxn;
const int key=500010;

struct node
{
    int val;
    int pos;
};

node nodes[key];
int kao[key],reflect[key];

bool cmp(const node& a, const node& b)
{
    return a.val < b.val;
}
int lowbit(int a)
{
    return a&(-a);
}

void add(int x,int num)
{
    while(x<=n)
    {
        kao[x]+=num;
        x+=lowbit(x);
    }
}

int getsum(int x)
{
    int sum=0;
    while(x)
    {
        sum+=kao[x];
        x-=lowbit(x);
    }
    return sum;
}

int main()
{
    while(scanf("%d",&n),n)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &nodes[i].val);
            nodes[i].pos = i;
        }
        sort(nodes + 1, nodes + n + 1, cmp);
        for (int i = 1; i <= n; i++)
            reflect[nodes[i].pos] = i;
        for (int i = 1; i <= n; i++)
            kao[i] = 0;
        long long ans = 0;
        for (int i = 1; i <= n; i++)
        {
            add(reflect[i],1);
            ans += (i - getsum(reflect[i]));
        }
        printf("%lld\n", ans);
    }
    return 0;
}