CSU 1532: JuQueen(线段树)-白红宇

强烈建议你试试无所不能的chatGPT，快点击我

CSU 1532: JuQueen(线段树)

阅读量：4596 次

发布时间：2019-06-09

本文共 3135 字，大约阅读时间需要 10 分钟。

1532: JuQueen

Time Limit: 5 Sec

Memory Limit: 512 MB

Submit: 363

Solved: 110

[ ][ ][ ]

Description

Input

Output

Sample Input

10 10 5state 0groupchange 2 9 7state 9groupchange 0 2 10change 0 -5

Sample Output

0773-3

HINT

题意：输入：c n q ->给你初始[0,c)去为0的区间，q个操作，n是区间数的上限，即不能超过n

q次操作： state id 输出下标为id 的数

groupchange l r val 区间【l,r】上的每一个数：val>0。加1 val次，假设有一个数==n,停止操作。

val<0,减1 val次。假设有一个数==0，停止操作；输出实际加或减的次数。

change l val 同上，改为单点操作

题解：线段树维护区间最大值计最小值。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #define N 4587530#define Mod 10000007#define lson l,mid,idx<<1#define rson mid+1,r,idx<<1|1#define lc idx<<1#define rc idx<<1|1const double EPS = 1e-11;const double PI = acos ( -1.0 );const double E = 2.718281828;typedef long long ll;const int INF = 100010;using namespace std;struct node { int Max; int Min; int se;} tree[N<<2];int n,c,q;int Max,Min;void push_up(int idx) { tree[idx].Max=max(tree[lc].Max,tree[rc].Max); tree[idx].Min=min(tree[lc].Min,tree[rc].Min);}void build(int l,int r,int idx) { tree[idx].se=0; if(l==r) { tree[idx].Max=0; tree[idx].Min=0; return; } int mid=(l+r)>>1; build(lson); build(rson); push_up(idx);}void push_down(int idx) { if(tree[idx].se) { tree[lc].se+=tree[idx].se; tree[rc].se+=tree[idx].se; tree[lc].Max+=tree[idx].se; tree[lc].Min+=tree[idx].se; tree[rc].Max+=tree[idx].se; tree[rc].Min+=tree[idx].se; tree[idx].se=0; }}void updata(int l,int r,int idx,int x,int y,int val) { if(l>=x&&r<=y) { tree[idx].Max+=val; tree[idx].Min+=val; tree[idx].se+=val; return; } push_down(idx); int mid=(l+r)>>1; if(x<=mid)updata(lson,x,y,val); if(y>mid)updata(rson,x,y,val); push_up(idx);}int query(int l,int r,int idx,int x,int y) { if(l>=x&&r<=y) { Min=min(tree[idx].Min,Min); return tree[idx].Max; } push_down(idx); int mid=(l+r)>>1; int res=0; if(x<=mid)res=max(res,query(lson,x,y)); if(y>mid)res=max(res,query(rson,x,y)); return res;}int main() { //freopen("in.txt","r",stdin); while(~scanf("%d%d%d",&c,&n,&q)) { char s[20]; int l,r,val; build(1,c,1); while(q--) { scanf("%s",s); if(s[0]=='s') { scanf("%d",&l); printf("%d\n",query(1,c,1,l+1,l+1)); } else if(s[0]=='g') { scanf("%d%d%d",&l,&r,&val); Min=INF; if(val==0) { printf("0\n"); continue; } int x=query(1,c,1,l+1,r+1); // printf("x=%d\n",x); if(val>0) { if(n-x>=val) { printf("%d\n",val); updata(1,c,1,l+1,r+1,val); } else { printf("%d\n",n-x); updata(1,c,1,l+1,r+1,n-x); } } else { int v=-val; if(Min>=v) { printf("%d\n",val); updata(1,c,1,l+1,r+1,val); } else { printf("%d\n",-1*Min); updata(1,c,1,l+1,r+1,-1*Min); } } } else { scanf("%d%d",&l,&val); if(val==0) { printf("0\n"); continue; } Min=INF; int x=query(1,c,1,l+1,l+1); if(val>0) { if(n-x>=val) { printf("%d\n",val); updata(1,c,1,l+1,l+1,val); } else { printf("%d\n",n-x); updata(1,c,1,l+1,l+1,n-x); } } else { int v=-val; if(Min>=v) { printf("%d\n",val); updata(1,c,1,l+1,l+1,val); } else { printf("%d\n",-1*Min); updata(1,c,1,l+1,l+1,-1*Min); } } } } } return 0;}

转载于:https://www.cnblogs.com/jzdwajue/p/7229390.html

你可能感兴趣的文章

linux上很方便的上传下载文件工具rz和sz使用介绍

React之特点及常见用法

【WEB前端经验之谈】时间一年半,或沉淀、或从零开始。

优云软件助阵GOPS·2017全球运维大会北京站

linux 装mysql的方法和步骤

poj3667(线段树区间合并&区间查询)

51nod1241(连续上升子序列)

SqlSerch 查找不到数据

集合相关概念

Memcache 统计分析！

(Python第四天)字符串

使用python动态特性时，让pycharm自动补全

关于R软件的安装

MySQL数据库免安装版配置

你必知必会的SQL面试题

html5 Canvas绘制时钟以及绘制运动的圆

Unity3D热更新之LuaFramework篇[05]--Lua脚本调用c#以及如何在Lua中使用Dotween

JavaScript空判断

洛谷 P1439 【模板】最长公共子序列（DP，LIS？）

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2024-10-19 03:25:41 当前IP: 18.119.253.168 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我