正文

bzoj1513

123456  123456  2022-09-17  402

关键词：

二维线段树

听说二维线段树不能下传标记？

就是裸的二维线段树，由于每次高度只能增加，所以我们就可以标记永久化

每个线段树里有两个数组,mx和mark，每次修改路径上所有mx都要修改，mark是区间的精确覆盖修改

每次查询把路径上所有mark取max，然后和精确覆盖区间mx取max

为什么这样做呢？我们能不能只用一个数组？当然不行，如果我们只用mark，那么假设我们更新区间[1,4],然后查询区间[1,5],那么答案明显不对，如果我们只用mx，那么我们更新[1,1],查询[2,2],那么我们的答案被[1,1]更新了，也是不对。

#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
int n, m, t;
struct Segment_Tree_X {
    int mx[N], mark[N];
    void update(int l, int r, int x, int a, int b, int tmp)
    {
        if(l > b || r < a) return;
        mx[x] = max(mx[x], tmp);
        if(l >= a && r <= b) 
        {
            mark[x] = max(mark[x], tmp);
            return;
        }
        int mid = (l + r) >> 1;
        update(l, mid, x << 1, a, b, tmp);
        update(mid + 1, r, x << 1 | 1, a, b, tmp);
    }
    int query(int l, int r, int x, int a, int b)
    {
        if(l > b || r < a) return 0;
        if(l >= a && r <= b) return mx[x];
        int mid = (l + r) >> 1;
        return max(mark[x], max(query(l, mid, x << 1, a, b), query(mid + 1, r, x << 1 | 1, a, b)));
    }
};
struct Segment_Tree_Y {
    Segment_Tree_X mx[N], mark[N];
    void update(int l, int r, int x, int a, int b, int y_l, int y_r, int tmp)
    {
        if(l > b || r < a) return;
        mx[x].update(1, m, 1, y_l, y_r, tmp);
        if(l >= a && r <= b)
        {
            mark[x].update(1, m, 1, y_l, y_r, tmp);
            return;
        }
        int mid = (l + r) >> 1;
        update(l, mid, x << 1, a, b, y_l, y_r, tmp);
        update(mid + 1, r, x << 1 | 1, a, b, y_l, y_r, tmp);
    }
    int query(int l, int r, int x, int a, int b, int y_l, int y_r)
    {
        if(l > b || r < a) return 0;
        if(l >= a && r <= b) return mx[x].query(1, m, 1, y_l, y_r);
        int mid = (l + r) >> 1;
        return max(mark[x].query(1, m, 1, y_l, y_r), max(query(l, mid, x << 1, a, b, y_l, y_r), query(mid + 1, r, x << 1 | 1, a, b, y_l, y_r)));
    }
} T;
int main()
{
    scanf("%d%d%d", &n, &m, &t);
    while(t --)
    {
        int d, s, w, x, y, tmp;
        scanf("%d%d%d%d%d", &d, &s, &w, &x, &y);
        ++ x;
        ++ y;
        tmp = T.query(1, n, 1, x, x + d - 1, y, y + s - 1);
        T.update(1, n, 1, x, x + d - 1, y, y + s - 1, w + tmp);
    }
    printf("%d
", T.query(1, n, 1, 1, n, 1, m));
    return 0;
}

View Code

bzoj1513[poi2006]tet-tetris3d二维线段树

题目链接BZOJ1513题解真正地理解了一波线段树标记永久化的姿势每个节点维护两个值$v$和$tag$$v$代表儿子中的最值$tag$代表未下传的最值显然节点的区间大于等于$v$的实际区间而$tag$的区间包含节点的区间我们在修改的时... 查看详情

bzoj1513:[poi2006]tet-tetris3d

Description三维空间从上落下几个长方体,问最后的最高高度.Solution二维线段树.感觉这种东西是可以yy出来的吧..对行建线段树,再对列建线段树维护行的信息,注意打标记的位置,和返回的时候一定要记得统计上标记.开4倍内存会MLE...Co... 查看详情

bzoj1513[poi2006]tet-tetris3d二维线段树

【BZOJ1513】[POI2006]Tet-Tetris3DDescriptionTask:Tetris3D"Tetris"游戏的作者决定做一个新的游戏,一个三维的版本,在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.作者想改变一下游戏的目的... 查看详情

[bzoj1513]tet-tetris3d

get了新的标记永久化技能～这题要求询问max和覆盖，因为是线段树套线段树，所以内外都不可以标记下传这种标记永久化的套路是维护两个标记：$mx,all$，$mx$表示这个子树内的真最大值，$all$表示整个子树曾经被覆盖过这样的最... 查看详情

bzoj1513[poi2006]tet-tetris3d（二维线段树）

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1513 【题目大意】　　一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.　　你将知道落下的立方体信息以及位置,　　你的任务就是回答所有立方... 查看详情

bzoj1513[poi2006]tet-tetris3d(代码片段)

二维线段树板子，注意标记永久化。1#include<bits/stdc++.h>2usingnamespacestd;3intans,A,B,n,ql,qr,qd,qu;4structQuerx56intv[3005],tag[3005];7voidchange(intk,intl,intr,intL,intR,intw)89v[k]=max(v[k],w);10if(l==L&a 查看详情

bzoj1513:[poi2006]tet-tetris3d

DescriptionTask:Tetris3D"Tetris"游戏的作者决定做一个新的游戏,一个三维的版本,在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.作者想改变一下游戏的目的使得它更大众化,在新游戏... 查看详情

bzoj3261:最大异或和[可持久化trie]

3261:最大异或和TimeLimit: 10Sec MemoryLimit: 512MBSubmit: 1513 Solved: 657[Submit][Status][Discuss]Description给定一个非负整数序列{a}，初始长度为N。 &n 查看详情

ural1513lemontale

URAL1513思路：dp+高精度状态：dp[i][j]表示长度为i末尾连续j个L的方案数初始状态：dp[0][0]=1状态转移：dp[i][j]=dp[i-1][j-1](0<=j<=k) dp[i][0]=∑dp[i-1][j](0<=j<=k)目标状态：dp[n+1] 查看详情

ural1513.lemontale(简单的递推)

...水题啊。就当熟悉一下java了啊。num[i]=2*num[i-1]-num[i-2-k]。1513.LemonTaleTimelimit:1.0secondMemorylimit:64MBBackgroundForeachprogrammerapointcomeswhenthelastcontestislo 查看详情

uva1513(树状数组)

既然不能把树状数组的开头当作顶端，就把树状数组的结尾当作顶端，不断清空要拿走的片子，并更新结尾#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>usingnamespacestd;constintmaxn=100000+100;intss[maxn*2],pos 查看详情

sdnu1513字符串翻转

1513.K.ReversedWordsTimeLimit:2000MS MemoryLimit:32768KBTotalSubmission(s): 56 AcceptedSubmission(s): 31DescriptionSomealiensarelearningEnglish.Theyhaveaverystrangewayinwritingthattheyreveredeverywordinthesentencebutkeepallthewordsincommonorder.Forexamplewhenthe... 查看详情

hdu1513[palindrome]回文串

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1513题目大意：给一个字符串，问最少加多少个字母能成为回文串。关键思想：要解决的是回文子序列问题而不是回文子串。回文子序列怎么求？可以把字符串倒转一下，再求他们的最... 查看详情

51nod1513

题解：更据题意，在树上深度为没一个数的都放在一起，要用的时候二分出来，看结果用c++的数据结构代码：#include<bits/stdc++.h>usingnamespacestd;constintN=5e5+10,L=27;chars[N];intn,m,cnt=0,max_h=0,high[N];vector<int>E[N],A[N],B[N];pair<int 查看详情

1513.numberofsubstringswithonly1s(代码片段)

Givenabinarystring s (astringconsistingonlyof‘0‘and‘1‘s).Returnthenumberofsubstringswithallcharacters1‘s.Sincetheanswer maybetoolarge, returnitmodulo 10^9+7. Example1:Inp 查看详情

hihocoder#1513:小hi的烦恼bitset(代码片段)

目录题目链接题解代码题目链接hihocoder#1513:小Hi的烦恼题解cdq套cdq套cdq套cdq就完了呀对每一科开n个bitset表示该科目前i个有谁每次查询都&起来就好了代码#include<cstdio>#include<bitset>#include<cstring>#include<algorithm>#def... 查看详情

uva1513moviecollection(树状数组)

题意：给定给你一叠DV，编号1到n，1在最上面，n在最下面。然后现在给你m个操作，每次都指定一张CD，问要拿走这个CD需要挪走上面多少张CD，并且这个要拿走的CD放在这个叠CD的顶端。析：这个题要倒着来做，我就是正着做的，... 查看详情

hihocoder1513小hi的烦恼(代码片段)

传送门分析论bitset的妙用......我们利用桶排将输入的数据排序，之后分别考虑5维，a[i][j]表示考虑第i个人第j维的情况下于其它人的大小关系。最后将5维的信息并起来求1的个数即可代码#include<iostream>#include<cstdio>#include<... 查看详情