首页 > 其他分享 >线段树

线段树

时间:2023-07-22 11:55:35浏览次数:47  
标签:int 线段 tr mid build query op

//单点修改查询
//http://ybt.ssoier.cn:8088/problem_show.php?pid=1549
//https://www.luogu.com.cn/problem/P1198
//用一维数组来存,当作完全二叉树来存
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
long long int m,p,n,last,t;
char op;
struct node
{
    int l,r,v;
}tr[N*4];
void pushup(int u)//更新每个区间的最大值
{
    tr[u].v=max(tr[u*2].v,tr[2*u+1].v);
}
void build(int u,int l,int r)//建立线段树
{
    tr[u]={l,r};
    if(l==r) return;
    int mid=l+r>>1;
    build(2*u,l,mid),build(2*u+1,mid+1,r);//向左建立,向右建立
}
int query(int u,int l,int r)//查询
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].v;
    int mid=tr[u].l+tr[u].r>>1,v=0;
    if(l<=mid) v=query(2*u,l,r);
    if(r>mid) v=max(v,query(2*u+1,l,r));
    return v;
}
int modify(int u,int x,int v)//修改
{
    if(tr[u].l==x&&tr[u].r==x) tr[u].v=v;
    else{
        int mid=tr[u].l+tr[u].r>>1;
        if(x<=mid) modify(2*u,x,v);
        else modify(2*u+1,x,v);
        pushup(u);
    }
}
int main()
{
    cin>>m>>p;
    build(1,1,m);
    while(m--){
        cin>>op>>t;
        if(op=='Q'){
            last=query(1,n-t+1,n);
            cout<<last<<endl;
        }
        else{
            modify(1,n+1,(last+t)%p);
            n++;
        }
    }
    return 0;
}

 

标签:int,线段,tr,mid,build,query,op
From: https://www.cnblogs.com/o-Sakurajimamai-o/p/17573099.html

相关文章

  • 【codevs3012】线段覆盖4
      #include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;structhp{ intai,bi,ci;}a[1005];boolcmp(hpa,hpb){ returna.bi<b.bi;}constintM=1e6+2;intn,i,j,k,maxn,f[1005];int......
  • 【模板】线段树优化建图
    区间连区间luoguP6348[PA2011]Journeys略带卡常#include<bits/stdc++.h>usingnamespacestd;vector<pair<int,int>>e[4200001];intdis[4200001],id[4200001];intlson(intl){returnl*2;}intrson(intl){returnl*2+1;}voidbuild(int......
  • 洛谷 P8861 - 线段
    牛逼题。先考虑\(l\le10^5,10^5+1\ler\)的部分分:一种方法是线段树,即因为左右端点是独立的,因此对左右端点各维护一个权值线段树表示有多少个区间以这个值为左/右端点,这样对于修改,左端点的部分相当于先查询\(\lel\)的数的个数,然后将它们都挂到\(l\)上,最后把\(<l\)的部......
  • 线段树--区间最大值模板
    Smiling&Weeping----你是我绕过的山河错落,才找到的人间烟火ProblemDescriptionThereisasequence a oflength n.Weuse ai todenotethe i-thelementinthissequence.Youshoulddothefollowingthreetypesofoperationstoth......
  • 线段树hdu-4027
    Smiling&Weeping ----姑娘,倘若,我双手合十的愿望里有你呢ProblemDescriptionAlotofbattleshipsofevilarearrangedinalinebeforethebattle.Ourcommanderdecidestouseoursecretweapontoeliminatethebattleships.Ea......
  • 在线CAD如何配合three.js绘制带线宽的线段
    前言1.在线CAD的产品经常会被集成到很多用户的网页系统内,前端开发人员只要会JavaScript,就可以对在线CAD进行集成和二次开发,今天这篇文章我们讲一下梦想CAD控件云图(H5方式)如何配合three.js绘制带线宽的线段。2.在这之前,如果还没有安装梦想CAD控件的朋友,可以查看快速入门,链接如......
  • 浅谈虚树优化线段树
    前言我们都知道动态开点权值线段树的空间复杂度是\(O(n\logV)\)的,但是很多题目中这样的空间是会被卡的,那我们能不能优化呢?实现看看下面这一棵树:在上图中,红色节点使我们平常会开的点。但是我们发现,其实只要维护绿色的点和红色的叶子结点。其实,绿色节点就是所有叶子结点......
  • 线段树分治结构
    目录线段树分治结构基本知识:例题1: 模板(基础题)例题2: dp(背包)(会了就掌握题)线段树分治结构基本知识:应用点: 当有些东西一会出现,一会又不出现时,可以使用线段树分治方式: 维护某一个东西出现的时间段,并在线段树上打上标记,并dfs遇到标记后,就相当于加入了这个物品。当dfs到叶子节点后,就......
  • 纯css 四边形的角样式(只有两个角是三角,其他两个是线段)
    效果如图:核心:使用伪类代码如下:<divclass="box-style"></div>.box-style{position:relative;//纯css只有四个角有边框的样式box-shadow:0px0px12px1px#003ba26binset;background:linear-gradient(toleft,#1f5fd3,#1f5fd3)lefttopno-repeat,......
  • 线段树模板
    单点修改,区间查询给n个数a1,a2,a3,…,an。支持q个操作:1xd,修改ax=d。2lr,查询(l,r),并且求出最小值出现了多少次。输入格式第一行两个整数n,q(1≤n,q≤2×105)。接下来一行n个整数a1,a2,…,an(1≤ai≤109)。接下来q行,每行一个形如1xd或者2lr的操作,保证1≤x≤n,......