SP1557 GSS2 - Can you answer these queries II

SP1557 GSS2 - Can you answer these queries II

题意

求区间最大去重后的子段和。

Solution

考虑到 CF997E 的套路。求区间子段计数的问题，可以采用离线的方式。还是一样考虑移动右端点。那么在线段树上 \(i\) 位置存储 \([i,r]\) 的去重后的子段和。

现在考虑端点移动。加入了一个 \(a_r\)，只会对上一次出现 \(a_r\) 的位置之后的位置的值产生影响。所以我们开一个数组，记录一下每个值上一次出现的位置即可，然后在线段树上做区间加。

然后考虑统计答案。对于求区间中最大子区间，同样需要把历史最值给记录下来。和 CF997E 一样，我们考虑通过在线段树上打标记，来记录每一个左端点到右端点最大值的最大值。为了保证复杂度，我们同样需要打一个标记，表示这段区间是否需要取一下区间最大值存到历史最值里去。

写了一下发现了一点问题，只记录是否需要取最大值是不够的，因为有可能当前最优值没有下放然后后面修改的时候直接把这个状态覆盖掉了。所以我们需要把这个标记改成从上一次下放开始到当前加法标记的最大值，这样的话下放的时候直接用这个标记来更新历史最值就不会丢失更优状态了。

Code

const int MAXN=2e5+10;const int dlt=1e5;int a[MAXN],pre[MAXN];vectorpii qs[MAXN];struct Tree{int l,r,sum,inc,mx,tag;}tr[MAXN2];#define ls i1#define rs i1|1void pushup(int i){tr[i].sum=max(tr[ls].sum,tr[rs].sum);tr[i].mx=max(tr[ls].mx,tr[rs].mx);}void add(int i,int v,int t){tr[i].sum+=v;tr[i].tag=max(tr[i].tag,tr[i].inc+t);tr[i].inc+=v;}void pushdown(int i){tr[ls].mx=max(tr[ls].mx,tr[ls].sum+tr[i].tag);tr[rs].mx=max(tr[rs].mx,tr[rs].sum+tr[i].tag);add(ls,tr[i].inc,tr[i].tag);add(rs,tr[i].inc,tr[i].tag);tr[i].inc=tr[i].tag=0;}void build(int i,int l,int r){tr[i].l=l;tr[i].r=r;tr[i].inc=tr[i].tag=tr[i].mx=0;if(l==r){tr[i].sum=0;return;}int mid=(l+r)1;build(ls,l,mid);build(rs,mid+1,r);pushup(i);}void upd(int i,int l,int r,int v){if(tr[i].l==ltr[i].r==r){tr[i].sum+=v;tr[i].mx=max(tr[i].mx,tr[i].sum);tr[i].inc+=v;tr[i].tag=max(tr[i].tag,tr[i].inc);return;}pushdown(i);int mid=(tr[i].l+tr[i].r)1;if(r=mid) upd(ls,l,r,v);else if(lmid) upd(rs,l,r,v);else upd(ls,l,mid,v),upd(rs,mid+1,r,v);pushup(i);}int ask(int i,int l,int r){if(tr[i].l==ltr[i].r==r) return tr[i].mx;pushdown(i);int mid=(tr[i].l+tr[i].r)1;if(r=mid) return ask(ls,l,r);else if(lmid) return ask(rs,l,r);else return max(ask(ls,l,mid),ask(rs,mid+1,r));}int ans[MAXN];signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cinn;rep(i,1,n) cina[i];int Q;cinQ;rep(i,1,Q){int l,r;cinlr;qs[r].pb(mkp(l,i));}build(1,1,n);rep(i,1,n){upd(1,pre[a[i]+dlt]+1,i,a[i]);pre[a[i]+dlt]=i;for(auto p:qs[i])ans[p.se]=max(0ll,ask(1,p.fi,i));}rep(i,1,Q) coutans[i]'\n';return 0;}

SP1557 GSS2 - Can you answer these queries II 相关文章

1. Can you answer these queries III （线段树）
   

   Can you answer these queries III （线段树） #includebits/stdc++.h#define size 500005using namespace std;int a[size];struct tree{ int l,r; ///l,r左右端点 int data; ///data区间最大子序列和 int lmax; ///lmax区间左端点开头的最大连续子序列和 int

2. 在PL/SQL 里面有把锁一样的按钮，点击它会跳出“these query res
   

   在PL/SQL 里面有把锁一样的按钮，点击它会跳出“these query result are not updateable，include the ROWID to get updateab 在PL/SQL 里有把锁一样的按钮，点击它会跳出“these query result are not updateable，include the ROWID to get updateab” 一

3. SP20644 ZQUERY - Zero Query
   

   题面传送门 考虑前缀和后转化为区间最长相等数距离。 那么可以回滚莫队解决。 回滚莫队是什么呢适用于一些只能增加而很难减少的情况。 将莫队左端点在一个块时，右端点升序排序，同时维护最左和最右即可。 代码实现: #i...

4. Even better if you don’t want to answer and
   

   Even better, if you don’t want to answer and Even better, if you don’t want to answer and don’t want to hang up, just slide the banner up to ignore. The other party is still dialing and you are not affected at all; if you want to answer

5. 2. 机器学习基石-When can Machine Learn? - Learning to Answer
   

   2. 机器学习基石-When can Machine Learn? - Learning to Answer Yes or No When can Machine Learn? - Learning to Answer Yes or No When can Machine Learn? - Learning to Answer Yes or No 1. Perceptron Hypothesis Set 1) Perceptron Hypothesis Set

6. Error querying database. Cause: org.springframework.jdbc.Can
   

   Error querying database. Cause: org.springframework.jdbc.CannotGetJdbcConnectionException报错 写了Controller类返回json数据文件时候报错 This application has no explicit mapping for /error, so you are seeing this as a fallback. 回到idear发现

7. 002-CANoe 10.0 SP3 软件和CAN卡的配置笔记
   

   002-CANoe 10.0 SP3 软件和CAN卡的配置笔记 目录 1，CANoe软件打开后的界面如下： 2，离线回放数据：Analysis→Measurement Setup 3，模拟数据输入设置：Simulation→Simulation Setup→I-Generator→右键IG模块→Block Active开启 4，CAN通道的dbc文件加载

8. Can you solve this equation
   

   Can you solve this equation Now,given the equation 8*x^4 + 7*x^3 + 2*x^2 + 3*x + 6 == Y,can you find its solution between 0 and 100; Now please try your lucky. Input The first line of the input contains an integer T(1=T=100) which means th

9. [SQL] Query 1009erp start [ERR] 1064 - You have an error in
   

   [SQL] Query 1009erp start [ERR] 1064 - You have an error in your SQL syntax； check the manual that c CREATE TABLE `bus_inport` ( `id` int(11) NOT NULL AUTO_INCREMENT, `paytype` varchar(255) CHARACTER SET utf8 COLLATE utf8_general_ci NULL D

10. 1423. Maximum Points You Can Obtain from Cards
    

    仅供自己学习 思路： 因为之前做了滑动窗口的题，可以用来求连续子串的最大值，最小值，那么是不是可以换一个方向，因为从两侧取值不连续，但我们可以取 在中部取连续的 s-k个数，并且求最小值，再用所有数字和减去最...

11. Leetcode 1561. Maximum Number of Coins You Can Get
    

    Leetcode 1561. Maximum Number of Coins You Can Get Leetcode 1561. Maximum Number of Coins You Can Get 题目 解法1：heap 解法2：sort 题目 解法1：heap 这道题的规律是，每次取剩下堆中的最大的两个值和最小的值组成triplet就可以，剩下的只是实现问题

12. 4 Things You Can Do with Alibaba Cloud PolarDB
    

    4 Things You Can Do with Alibaba Cloud PolarDB During the PolarDB session of the 2017 Computing Conference, Alibaba Cloud's high level Technical Expert He Jun delivered a speech on the features and common use cases of PolarDB. In his speec

13. Quartus II 13.0 sp1的官方下载页面
    

    今天为了下个ModelSim跑到网上去找下载资源，清一色的百度网盘，下载速度60k/s，简直有病，于是跑到Intel官网上把连接挖出来了，供各位直接下载 实测使用IDM多线程下载速度可以轻松上到数MB/s,下面上链接 https://www.intel.com/content...

14. android studio-打包报Errors while building APK. You can find
    

    android studio-打包报Errors while building APK. You can find the errors in the 'Messages' view.报错解决方案 android打包报错: 控制台报错解决方案:Error:Error converting bytecode to dex: Cause: com.android.dex.DexIndexOverflowException: Canno

15. MySql报错 1093 - You can’t specify target table xxx for upd
    

    MySql报错 1093 - You can’t specify target table xxx for update in FROM clause 写在前面 ： 我是 「扬帆向海」，这个昵称来源于我的名字以及女朋友的名字。我热爱技术、热爱开源、热爱编程。 技术是开源的、知识是共享的 。 这博客是对自...

16. You can't specify target table 'Person&#
    

    DELETE FROM Persons WHERE Id NOT IN ( SELECT MIN (Id) AS id FROM Persons GROUP BY Email) ; Youcan"tspecifytargettable"Person"forupdateinFROMclause 问题出现：同一个表里删除操作 和查询连同一起了 把后半句 (SELECT MIN(Id)AS id FROM Persons GRO

17. IDEA 踩坑之maven 打包提示 Cannot find JRE '1.8-Z'. You can s
    

    IDEA 踩坑之：maven 打包提示 Cannot find JRE '1.8-Z'. You can specify JRE to run maven ... IDEA 在maven打包时出现如下情况： 分析原因：系统没有找到 JRE'1.8-Z' 解决思路：找不到系统的，我们就自己指定JDK。 解决办法： （1）点击【File】-【Settin...

18. mysql：[Err] 1093 - You can‘t specify target table ‘at_pho
    

    mysql：[Err] 1093 - You can‘t specify target table ‘at_phone‘ for update in FROM clause问题 原始sql delete from at_phone where id not in(select id from at_phone where id!=1) 运行这段sql语句，结果报错 [Err] 1093 - 您不能在FROM子句中指定目

19. 如何解决“This app is damaged and can’t be opened. You shou
    

    如何解决“This app is damaged and can’t be opened. You should move it to the Trash” 参考资料： https://osxdaily.com/2019/02/13/fix-app-damaged-cant-be-opened-trash-error-mac/ 在外网上下了个app，但是打不开，显示的是如下的图片：(参考资料里

20. Ubuntu16.04 （ROS）下通过CAN分析仪（USBCAN/CANalyst-II）调试
    

    Ubuntu16.04 （ROS）下通过CAN分析仪（USBCAN/CANalyst-II）调试无人车助力转向电机（1） 调试流程 1、测试USBCAN/CANalyst-II工作是否正常 2、使用PC端的上位机测试转向电机是否正常及指令测试 3、测试USBCAN/CANalyst-II提供的Linux x64的例程 4、...