首页 > 其他分享 >P5854 【模板】笛卡尔树

P5854 【模板】笛卡尔树

时间:2024-07-04 17:09:43浏览次数:15  
标签:P5854 10000007 笛卡尔 ll 元素 top 节点 模板

原题链接

题解

笛卡尔树的定义如下:任意一颗子树都代表一段连续的区间,且子树的根节点是该区间的最大值,根的左边的元素下标均比根小(二叉搜索树性质),子节点均比父节点大(堆的性质)
我们讲如何实现的
设即将要插入的元素为 \(a_i\)
栈内的元素为前 \(i-1\) 个元素构成的笛卡尔树从根一直走右节点途径的节点(途径顺序为从栈底到栈顶)
如果 \(a_i\) 比栈顶元素小,则 \(r[st.top()]=i\),然后压入栈内
否则找到从栈底到栈顶最后一个比自己小的元素 \(x\),令 \(x\) 后面的第一个元素变成 \(a_i\) 的左子节点(剩余元素全部弹出,顺序不变),\(x\) 的右节点变为 \(a_i\) 然后压入栈内

code

#include<bits/stdc++.h>
using namespace std;

#define ll long long

ll a[10000007], l[10000007] = {0}, r[10000007] = {0};

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    ll n;
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];

    stack<ll> q;
    for (ll i = 1; i <= n; i++)
    {
        if (q.empty()) q.push(i);
        else
        {
            ll tem = 0;
            while (q.size() && a[q.top()] >= a[i])
            {
                tem = q.top();
                q.pop();
            }
            l[i] = tem;
            if (q.size()) r[q.top()] = i;
            q.push(i);
        }
    }

    ll ans1 = 0, ans2 = 0;
    for (ll i = 1; i <= n; i++)
    {
        ans1 ^= i * (l[i] + 1);
        ans2 ^= i * (r[i] + 1);
    }

    cout << ans1 << " " << ans2;
    return 0;
}

标签:P5854,10000007,笛卡尔,ll,元素,top,节点,模板
From: https://www.cnblogs.com/pure4knowledge/p/18284201

相关文章

  • 笛卡尔树
    笛卡尔树对于每个区间,找到区间的极值,把这个区间一分为二,这个极值就是这个区间的根,两个部分的根是极值的两个儿子如何求笛卡尔树?以大根堆为例方法一令\(l_i\)表示第\(i\)个元素向左第一个\(\ge\)它的位置,\(r_i\)表示第\(i\)个元素向右第一个\(\ge\)它......
  • 笛卡尔树
    引入首先我们看到这个序列\([9,4,10,1,7,2,3]\),现在我们找到它的最大值\(10\),并从中间劈开,此时分为了两个序列\([9,4]\)和\([1,7,2,3]\),接着对这两个序列继续这样的操作。现在,将劈开后序列最大值和被劈开的数建立父子关系,于是便建立了这个树:这也就是笛卡尔树。笛卡尔树满......
  • C++从淬体到元婴day10之模板
    2024/6/30模板概念:在C++中,模板是一种泛型编程的工具,它允许程序员编写与类型无关的代码。作用:通过使用模板,你可以编写一种可以处理多种数据类型的函数或类,而无需为每种数据类型编写单独的实现。分类:函数模板和类模板函数模板建立一个通用函数,其函数返回值类型和形参类......
  • 高精度模板
    转载自wkh2008。#include<bits/stdc++.h>usingnamespacestd;namespaceBIGINT{usingcpx=complex<double>;constdoublePI=acos(-1);vector<cpx>roots={{0,0},{1,0}};voidensure_capacity(intmin_capacity){for(intlen=r......
  • 【模板】树同构([BJOI2015]树的同构)
    一段合法的括号序和一棵有根树唯一对应,具体而言,考虑生成括号序的过程,从根节点出发,遇到左括号就向下走一步,遇到右括号就向上走一步由于树上的一个节点可能有多个子节点,因此在不规定访问顺序的情况下,同一棵树有多种不同的括号序列点击查看代码#include<bits/stdc++.h>using......
  • django使用jinja2模板
    1.使用Django默认模板TEMPLATES=[{'BACKEND':'django.template.backends.django.DjangoTemplates','DIRS':[BASE_DIR/'templates'],#使用路径表达式'APP_DIRS':True,'OPTIO......
  • CMD模板
    @echooffcolor09title打开网络中心控制面板%窗口标题%@echo-------------------------------------------@echo-------------------------------------------@echo-------------------------------------------@echo--------------这里可以写中文-------------@ec......
  • P4097 【模板】李超线段树 / [HEOI2013] Segment
    P4097【模板】李超线段树/[HEOI2013]Segment前言李超线段树并不是一种新的线段树,而是对一类题维护最值的过程做了改进,使线段树仍然有不错的复杂度。引入简要题意实现两种操作:在区间\([x_0,y_0]\)上加入一条两端为\((x_0,y_0)\),\((x_1,y_1)\)的线段。查询下标\(k......
  • 解决Vue template模板中单一根元素
    引言错误的用法会导致页面加载空白<template><divid="1">内容1<div><divid="2">内容2<div></template>解决Vue模板中单一根元素要求的问题及原理解析在Vue.js开发中,单一根元素的要求是确保Vue能够有效地编译和渲染组件的重要规则之一。本文将深入探讨这一......
  • 10、 Django-模板-templates
     模板语法#模板中的变量语法:{{var}}如果变量不存在、则插入空字符串#方法不能有参数{{int}}{{str}}{{list}}{{list.0}}{{dict}}{{dict.a}}#dict['a']{{func}}#传递函数{{class_......