P8037 [COCI2015-2016#7] Prokletnik

来源:https://www.cnblogs.com/rgw2010/p/18355760
-Advertisement-
Play Games

二維差分 為什麼我為OI淚目？因為我菜得離譜...... 引入 一維差分用來O(1)修改區間，配合上一維首碼和就是O(N)的查詢區間和。 差分為首碼和的逆運算。 二維差分同理。 接下來這道題就用二維差分來解決。 \(例題：地毯>>\) 地毯 題目描述 在 \(n\times n\) 的格子上有 \( ...


思路：

首先考慮離線。

設 \(Min-nxt_i\) 表示下一個小於 \(a_i\) 處的位置，\(Max-nxt_i\) 表示下一個大於 \(a_i\) 處的位置。

那麼 \([l,r]\) 是魔法區間當且僅當：

  • \(r\) 是 \([l,r]\) 的最大值，且 \(r < Min - nxt_l\)。

  • \(r\) 是 \([l,r]\) 的最小值，且 \(r < Max - nxt_l\)。

再令 \(Min-pre_i\) 表示上一個小於 \(a_i\) 處的位置，\(Max-pre_i\) 表示上一個大於 \(a_i\) 處的位置。

那麼我們可以對於每個 \(r\)，求出對應的 \(l\) 的氛圍：

  • 若 \(r\) 是 \([l,r]\) 的最大值，則 \(l \in [Max-pre_r+1,r]\)。

  • 若 \(r\) 是 \([l,r]\) 的最小值，則 \(l \in [Min-pre_r+1,r]\)。

則可以在掃描線掃到 \(r\) 時，對上述兩個區間更新答案；註意到對於 \(l\) 的答案是 \(r-l+1\)，那麼對於區間 \([a,b]\)，其的右端點若都是 \(r\)，要使得貢獻最大，應該選擇 \([a,r]\) 區間，但是有些點是無法對 \(r\) 造成貢獻的（對於這類點的處理見下文），於是我們需要找到 \([a,b]\) 內最小的能對 \(r\) 造成貢獻的點，維護一個 set 二分即可，需要支持刪除。

但是我們需要滿足 \(r < Min-nxt_l\) 或 \(r<Max-nxt_l\)，那麼可以在 \(Min-nxt_l\) 和 \(Max-nxt_l\) 處將 \(l\) 此處賦值為無窮小即可。

註意到就算 \(l\) 處被賦值為無窮小，即無法對 \(r\) 與 \(r\) 後面的數造成貢獻，但是其本身也有貢獻，需要用另外一個線段樹維護無法造成新貢獻的點的區間最大貢獻。

時間複雜度為 \(O((N+Q) \log^2 N)\)。

完整代碼：

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef int ll;
bool Begin;
const ll N=5e5+10;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
ll n,q,l,r,top;
ll a[N],ans[N],stk[N],Mi_pre[N],Ma_pre[N],Mi_nxt[N],Ma_nxt[N];
vector<ll> F[N],G[N];
vector<pi> Q[N];
class St{
public:
    ll X[N<<2];
    void pushup(ll k){
        X[k]=max(X[k<<1],X[k<<1|1]);
    }
    void build(ll k,ll l,ll r){
        X[k]=0;
        if(l==r)
          return ;
        ll mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
    }
    void add(ll k,ll l,ll r,ll i,ll v){
        if(l==i&&i==r){
            X[k]=v;
            return ;
        }
        ll mid=(l+r)>>1;
        if(i<=mid)
          add(k<<1,l,mid,i,v);
        else
          add(k<<1|1,mid+1,r,i,v);
        pushup(k);
    }
    ll query(ll k,ll L,ll R,ll l,ll r){
        if(L==l&&r==R)
          return X[k];
        ll mid=(L+R)>>1;
        if(r<=mid)
          return query(k<<1,L,mid,l,r);
        else if(l>mid)
          return query(k<<1|1,mid+1,R,l,r);
        else
          return max(query(k<<1,L,mid,l,mid),query(k<<1|1,mid+1,R,mid+1,r));
    }    
}TT;
class Tree{
public:
    set<ll> S;
    struct Node{
        ll l,r;
        ll Max;
        ll tag;
    }X[N<<2];
    ll get(ll x){
        return (*S.lower_bound(x));
    }
    void add(ll k,ll v){
        ll t=get(X[k].l);
        if(t>X[k].r)
          X[k].Max=-1e9;
        else
          X[k].Max=v-t+1;
        X[k].tag=v;
    }
    void push_down(ll k){
        if(X[k].tag){
            add(k<<1,X[k].tag);
            add(k<<1|1,X[k].tag);
            X[k].tag=0;
        }
    }
    void pushup(ll k){
        X[k].Max=max(X[k<<1].Max,X[k<<1|1].Max);
    }
    void build(ll k,ll l,ll r){
        X[k].l=l,X[k].r=r;
        X[k].tag=X[k].Max=0;
        if(l==r){
            S.insert(l);
            return ;
        }
        ll mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
    }
    void add(ll k,ll i,ll v){
        if(X[k].l==i&&i==X[k].r){
            TT.add(1,1,n,i,X[k].Max);
            S.erase(i);
            X[k].Max=v;
            return ;
        }
        push_down(k);
        ll mid=(X[k].l+X[k].r)>>1;
        if(i<=mid)
          add(k<<1,i,v);
        else
          add(k<<1|1,i,v);
        pushup(k);
    }
    void update(ll k,ll l,ll r,ll v){
        if(X[k].l==l&&r==X[k].r){
            //cerr<<"1:"<<l<<' '<<r<<' '<<v<<'\n';
            add(k,v);
            //cerr<<"2:"<<l<<' '<<r<<' '<<X[k].Max<<'\n';
            return ;
        }
        push_down(k);
        ll mid=(X[k].l+X[k].r)>>1;
        if(r<=mid)
          update(k<<1,l,r,v);
        else if(l>mid)
          update(k<<1|1,l,r,v);
        else{
            update(k<<1,l,mid,v);
            update(k<<1|1,mid+1,r,v);
        }
        pushup(k);
        //cerr<<"3:"<<X[k].l<<' '<<X[k].r<<' '<<X[k].Max<<'\n';
    }
    ll query(ll k,ll l,ll r){
        //cerr<<"4:"<<X[k].l<<' '<<X[k].r<<' '<<X[k].Max<<'\n';
        if(X[k].l==l&&r==X[k].r)
          return X[k].Max;
        push_down(k);
        ll mid=(X[k].l+X[k].r)>>1;
        if(r<=mid)
          return query(k<<1,l,r);
        else if(l>mid)
          return query(k<<1|1,l,r);
        else
          return max(query(k<<1,l,mid),query(k<<1|1,mid+1,r));
    }
}T;
bool End;
int main(){
    n=read();
    for(int i=1;i<=n;i++)
      a[i]=read();
    q=read();
    for(int i=1;i<=q;i++){
        l=read(),r=read();
        Q[r].push_back({l,i});
    }
    for(int i=1;i<=n;i++){
        while(top&&a[stk[top]]>a[i]){
            Mi_nxt[stk[top]]=i;
            top--;
        }
        stk[++top]=i;    
    }
    top=0;
    for(int i=1;i<=n;i++){
        while(top&&a[stk[top]]<a[i]){
            Ma_nxt[stk[top]]=i;
            top--;
        }
        stk[++top]=i;
    }
    top=0;
    for(int i=n;i>=1;i--){
        while(top&&a[stk[top]]>a[i]){
            Mi_pre[stk[top]]=i;
            top--;
        }
        stk[++top]=i;  
    }
    top=0;
    for(int i=n;i>=1;i--){
        while(top&&a[stk[top]]<a[i]){
            Ma_pre[stk[top]]=i;
            top--;
        }
        stk[++top]=i;       
    }
    for(int i=1;i<=n;i++){
        F[Mi_nxt[i]].push_back(i);
        G[Ma_nxt[i]].push_back(i);
    }
    T.build(1,1,n);
    TT.build(1,1,n);
    for(int i=1;i<=n;i++){
        for(auto v:F[i])
          T.add(1,v,-1e9);
        T.update(1,Ma_pre[i]+1,i,i);
        for(auto t:Q[i])
          ans[t.se]=max({ans[t.se],T.query(1,t.fi,i),TT.query(1,1,n,t.fi,i)});
    }
    T.build(1,1,n);
    TT.build(1,1,n);
    for(int i=1;i<=n;i++){
        for(auto v:G[i])
          T.add(1,v,-1e9);
        T.update(1,Mi_pre[i]+1,i,i);
        for(auto t:Q[i])
          ans[t.se]=max({ans[t.se],T.query(1,t.fi,i),TT.query(1,1,n,t.fi,i)});
    }
    for(int i=1;i<=q;i++){
        write(ans[i]);
        putchar('\n');
    }
	return 0;
}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • HTML 樣式
    title: 清除 Nuxt 狀態緩存：clearNuxtState date: 2024/8/7 updated: 2024/8/7 author: cmdragon excerpt: 摘要：本文介紹了Nuxt.js框架中clearNuxtState方法的使用，該方法用於清除useState管理的 ...
  • 給我5分鐘，保證教會你在vue3中動態載入遠程組件
    前言 在一些特殊的場景中（比如低代碼、減少小程式包體積、類似於APP的熱更新），我們需要從服務端動態載入.vue文件，然後將動態載入的遠程vue組件渲染到我們的項目中。今天這篇文章我將帶你學會，在vue3中如何去動態載入遠程組件。 歐陽寫了一本開源電子書vue3編譯原理揭秘，這本書初中級前端能看懂。 ...
  • IntersectionObserver + scrollIntoView 實現電梯導航
    電梯導航也被稱為錨點導航，當點擊錨點元素時，頁面內相應標記的元素滾動到視口。而且頁面內元素滾動時相應錨點也會高亮。電梯導航一般把錨點放在左右兩側，類似電梯一樣。常見的電梯導航效果如下，比如一些官方文檔中： 之前可能會用 getBoundingClientRect() 判斷元素是否在視口中來實現類似效 ...
  • HTML 段落
    CSS中span元素垂直居中【解決span元素內基線對齊問題】 在樣式的書寫中，我們常常使用以下方式實現垂直居中，若span元素內例外，解決辦法看文章最後 <div class="parent"> <span class="child">text</span> </div> 1.flex佈局方式垂直 ...
  • 全網最適合入門的面向對象編程教程：34 Python的內置數據類型-Python常用複合數據類型：元組和命名元組
    元組是不可變的序列類型，可以包含不同類型的元素。命名元組是元組的子類，它允許你為元組中的位置指定名稱，從而使代碼更加清晰，本文主要介紹了兩種元組的使用方法和應用場景。 ...
  • 醫療行業解決方案參考
    醫療行業解決方案互聯網醫院架構患者門戶：提供患者信息查詢、掛號、繳費等基本服務。 預約掛號：允許患者線上預約掛號，減少現場排隊等候時間。 掛號查詢：患者可以查詢掛號狀態和相關信息。 院內導診：提供院內導航服務，幫助患者快速找到診室或部門。 檢驗報告查詢：患者可以線上查詢檢驗結果。 檢查報告查詢：提供 ...
  • JavaSE基礎知識分享(五)
    寫在前面 前面講的是面向對象中的繼承思想，下麵讓我們來看看多態這部分的內容！ Java 面向對象概念概述 多態 概述：某一個事物在不同狀態下的多種狀態。 實現多態的三大前提： 要有繼承關係。 要有方法的重寫。 要有父類的引用指向子類對象。 訪問成員的特點： 成員變數：編譯時看左，運行時看左。 成員方 ...
  • 實習第一天，不小心透露了，我是拆遷戶
    2018年6月，大三暑假進行時 上班之前，我提前跟家裡人打過招呼了。 我說我已經拿到了實習的offer，明天就過去上班，離家裡很近，月薪3500，我騎自行車過去就行。 家裡人就說挺好的，讓我騎個電瓶車，這樣會快點，囑咐我好好乾。 這是我第一次正式上班，我還覺得挺神奇的，沒想到我都要上班了。 大學以前 ...
一周排行
    -Advertisement-
    Play Games
  • WPF 已知問題 監聽 WMI 事件導致觸摸失效
    示例項目結構 在 Visual Studio 中創建一個 WinForms 應用程式後，項目結構如下所示： MyWinFormsApp/ │ ├───Properties/ │ └───Settings.settings │ ├───bin/ │ ├───Debug/ │ └───Release/ ...
  • [STAThread]特性
    [STAThread] 特性用於需要與 COM 組件交互的應用程式，尤其是依賴單線程模型（如 Windows Forms 應用程式）的組件。在 STA 模式下，線程擁有自己的消息迴圈，這對於處理用戶界面和某些 COM 組件是必要的。 [STAThread] static void Main(stri ...
  • UWP WinUI3 傳入 AddHandler 的 RoutedEventHandler 類型與事件所需不匹配將拋出參數異常
    在WinForm中使用全局異常捕獲處理 在WinForm應用程式中，全局異常捕獲是確保程式穩定性的關鍵。通過在Program類的Main方法中設置全局異常處理，可以有效地捕獲並處理未預見的異常，從而避免程式崩潰。 註冊全局異常事件 [STAThread] static void Main() { / ...
  • .NET 多版本 WinForm 開源控制項庫 SunnyUI
    前言 給大家推薦一款開源的 Winform 控制項庫，可以幫助我們開發更加美觀、漂亮的 WinForm 界面。 項目介紹 SunnyUI.NET 是一個基於 .NET Framework 4.0+、.NET 6、.NET 7 和 .NET 8 的 WinForm 開源控制項庫，同時也提供了工具類庫、擴展 ...
  • .net core8 使用Swagger（附當前源碼）
    說明 該文章是屬於OverallAuth2.0系列文章，每周更新一篇該系列文章（從0到1完成系統開發）。 該系統文章，我會儘量說的非常詳細，做到不管新手、老手都能看懂。 說明：OverallAuth2.0 是一個簡單、易懂、功能強大的許可權+可視化流程管理系統。 有興趣的朋友，請關註我吧(*^▽^*) ...
  • WPF 什麼時候 VisualTreeHelper.GetDescendantBounds 將返回無窮大
    一、下載安裝 1.下載git 必須先下載並安裝git，再TortoiseGit下載安裝 git安裝參考教程：https://blog.csdn.net/mukes/article/details/115693833 2.TortoiseGit下載與安裝 TortoiseGit，Git客戶端，32/6 ...
  • C# 開源教程帶你輕鬆掌握數據結構與演算法
    前言 在項目開發過程中，理解數據結構和演算法如同掌握蓋房子的秘訣。演算法不僅能幫助我們編寫高效、優質的代碼，還能解決項目中遇到的各種難題。 給大家推薦一個支持C#的開源免費、新手友好的數據結構與演算法入門教程：Hello演算法。 項目介紹 《Hello Algo》是一本開源免費、新手友好的數據結構與演算法入門 ...
  • 第22篇 生成proto文件bat腳本
    1.生成單個Proto.bat內容 @rem Copyright 2016, Google Inc. @rem All rights reserved. @rem @rem Redistribution and use in source and binary forms, with or with ...
  • 記一次 .NET某上位機視覺程式 卡死分析
    一：背景 1. 講故事 前段時間有位朋友找到我，說他的窗體程式在客戶這邊出現了卡死，讓我幫忙看下怎麼回事？dump也生成了，既然有dump了那就上 windbg 分析吧。 二：WinDbg 分析 1. 為什麼會卡死 窗體程式的卡死，入口門檻很低，後續往下分析就不一定了，不管怎麼說先用 !clrsta ...
  • 醫學DICOM文件與PACS系統進行數據傳輸
    前言 人工智慧時代，人臉識別技術已成為安全驗證、身份識別和用戶交互的關鍵工具。 給大家推薦一款.NET 開源提供了強大的人臉識別 API，工具不僅易於集成，還具備高效處理能力。 本文將介紹一款如何利用這些API，為我們的項目添加智能識別的亮點。 項目介紹 GitHub 上擁有 1.2k 星標的 C# ...
所有分類