loj#6041. 「雅禮集訓 2017 Day7」事情的相似度(SAM set啟髮式合併 二維數點)

来源:https://www.cnblogs.com/zwfymqz/archive/2019/03/29/10624232.html
-Advertisement-
Play Games

題意 "題目鏈接" Sol 只會尾碼數組+暴躁莫隊套set$n \sqrt{n} \log n$但絕對跑不過去。 正解是SAM + set啟髮式合併 + 二維數點/ SAM + LCT 但是我只會第一種qwq 首先一個性質是兩個首碼的最長公共尾碼就是他們再parent樹上的LCA的len 那麼我們考 ...


題意

題目鏈接

Sol

只會尾碼數組+暴躁莫隊套set\(n \sqrt{n} \log n\)但絕對跑不過去。

正解是SAM + set啟髮式合併 + 二維數點/ SAM + LCT

但是我只會第一種qwq

首先一個性質是兩個首碼的最長公共尾碼就是他們再parent樹上的LCA的len

那麼我們考慮每個LCA的貢獻。

把詢問離線下來按右端點排序,對於當前點的子樹中的點有一個顯然的性質。

若存在四個點\(l, x, y, r\)滿足\(l < x < y < r\),那麼顯然\(l, r\)這對點是沒有意義的(因為每對點產生的貢獻都相同)。也就說我們在處理子樹的時候實際上有一堆點對用不到。我們可以通過set啟髮式合併來合併子樹,也就是說我現在有一堆點集,然後我考慮加入一個新點之後哪些點對會有用,顯然只有它與它的前驅/後繼這兩個點對是有用的。

因為合併的時候是啟髮式合併,所以總複雜度不會超過\(n \log^2 n\)

然後處理完之後就是一個二維數點取max問題了。

調起來有點自閉qwq

#include<bits/stdc++.h> 
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define pb push_back 
//#define int long long 
#define LL long long 
#define ull unsigned long long 
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int MAXN = 1e6 + 10, mod = 1e9 + 7, INF = 1e9 + 10;
const double eps = 1e-9;
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline LL add(A x, B y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}
template <typename A, typename B> inline void add2(A &x, B y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}
template <typename A, typename B> inline LL mul(A x, B y) {return 1ll * x * y % mod;}
template <typename A, typename B> inline void mul2(A &x, B y) {x = (1ll * x * y % mod + mod) % mod;}
template <typename A> inline void debug(A a){cout << a << '\n';}
template <typename A> inline LL sqr(A x){return 1ll * x * x * x;}
template <typename A, typename B> inline LL fp(A a, B p, int md = mod) {int b = 1;while(p) {if(p & 1) b = mul(b, a);a = mul(a, a); p >>= 1;}return b;}
template <typename A> A inv(A x) {return fp(x, mod - 2);}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, ans[MAXN];
char s[MAXN];
vector<Pair> Q[MAXN], P[MAXN];
vector<int> v[MAXN];
set<int> st[MAXN];
int ch[MAXN][2], len[MAXN], fa[MAXN], las = 1, root = 1, tot = 1;
void insert(int x, int id) {
    int now = ++tot, pre = las; las = now; len[now] = len[pre] + 1; 
    st[now].insert(id);

    for(; pre && !ch[pre][x]; pre = fa[pre]) ch[pre][x] = now;
    if(!pre) fa[now] = root;
    else {
        int q = ch[pre][x];
        if(len[q] == len[pre] + 1) fa[now] = q;
        else {
            int nq = ++tot; 
            fa[nq] = fa[q]; len[nq] = len[pre] + 1; 
            memcpy(ch[nq], ch[q], sizeof(ch[q]));
            for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = nq;
            fa[now] = fa[q] = nq;
        }
    }
}
void dfs(int x) {
    set<int> &S = st[x]; 
    for(auto &to : v[x]) {
        dfs(to);
    
        set<int> &Sto = st[to];
        if(Sto.size() > S.size()) swap(Sto, S);
        for(auto &nxt: Sto) {
            auto pos = S.insert(nxt).fi;
            if(pos != S.begin()) {
                auto pre = --pos; pos++;
            //  printf("%d %d %d\n", *pos, *pre, len[x]);
                P[*pos].pb({*pre, len[x]});
            }
            if((++pos) != S.end()) {
                pos--;
                auto nxt = ++pos; pos--;
                //printf("%d %d\n", *pos, *nxt);
                P[*nxt].pb({*pos, len[x]});
            }
            S.erase(nxt);
        }
        for(auto &nxt: Sto) S.insert(nxt);
    }
}
void Build() {
    for(int i = 1; i <= tot; i++) v[fa[i]].push_back(i);
    dfs(1);
    for(int i = 1; i <= N; i++) sort(Q[i].begin(), Q[i].end()), sort(P[i].begin(), P[i].end());
}
int mx[MAXN];
#define lb(x) (x & (-x))
void Add(int x, int val) {
    x = N - x + 1;
    while(x <= N) chmax(mx[x], val), x += lb(x);
}
int Query(int x) {
    x = N - x + 1;
    int ans = 0;
    while(x) chmax(ans, mx[x]), x -= lb(x);
    return ans;
}
void solve() {
    for(int i = 1; i <= N; i++) {
        int cur = Q[i].size() - 1;
        for(int j = P[i].size() - 1; j >= 0; j--) {
            while((~cur) && Q[i][cur].fi > P[i][j].fi) ans[Q[i][cur].se] = Query(Q[i][cur].fi), cur--;
            Add(P[i][j].fi, P[i][j].se);
        }
        while(~cur) 
            ans[Q[i][cur].se] = Query(Q[i][cur].fi), cur--;
        
    }
}
signed main() {
    //freopen("a.in", "r", stdin);
    N = read(); M = read();
    scanf("%s", s + 1);
    for(int i = 1; i <= N; i++) insert(s[i] - '0', i);
    for(int i = 1; i <= M; i++) {
        int l = read(), r = read();
        Q[r].pb({l, i});
    }
    Build();
    solve();
    for(int i = 1; i <= M; i++) cout << ans[i] << '\n';
    return 0;
}

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

-Advertisement-
Play Games
更多相關文章
  • 自定義 ThreadPoolExecutor 處理線程運行時異常 最近看完了 "ElasticSearch線程池模塊" 的源碼,感觸頗深,然後也自不量力地借鑒ES的 EsThreadPoolExecutor 重新造了一把輪子,對線程池的理解又加深了一些。在繼承 ThreadPoolExecutor實 ...
  • centos7下安裝python3總步驟分三步: 一、依賴解決: 1.安裝依賴包: yum install zlib-devel bzip2-devel openssl-devel ncurses-devel sqlite-devel readline-devel tk-devel gcc make ...
  • 1.實現Runnable介面,重載run(),無返回值 2.繼承Thread類,覆寫run() 使用時通過調用Thread的start()(該方法是native),再調用創建線程的run(),不同線程的run方法裡面的代碼交替執行。 不足:由於java為單繼承,若使用線程類已經有個父類,則不能使用該 ...
  • 使用Visual Studio新建一個空項目,項目命名為HelloMFC,完成後,打開項目屬性頁面,將配置屬性選項卡中的常規項打開,將其中的MFC的使用屬性欄改為:在靜態庫中使用MFC或者在共用DLL中使用MFC,同時將字元集屬性欄改為使用Unicode字元集。 圖1-1 新建一個空項目 圖1-2 ...
  • 本文以JDK 1.8為例,包路徑rt.jar java.util.lang 1 HashMap原理 在bucket中存儲鍵對象和值對象,作為Map.Entry。使用put(key,value)存儲對象到HashMap中,使用get(key)從HashMap中獲取對象。當我們給put方法傳遞鍵值的時候 ...
  • 如果你用過BottomNavigationBar、TabBar、還有Drawer,你就會發現,在切換頁面之後,原來的頁面狀態就會丟失。 要是上一頁有一個數據列表,很多數據,你滾動到了下頭,切換頁面後,想再看一下下頭的數據,但是Flutter給你重回頁面了。。。 這誰能頂得住啊。 看了一下解釋,原來F ...
  • 1. 誰該閱讀這篇文章 本文是關於削減C語言程式記憶體占用空間的一項技術——為了減小記憶體大小而手工重新封裝C結構體聲明。你需要C語言的基本知識來讀懂本文。 如果你要為記憶體有限制的嵌入式系統、或者操作系統內核寫代碼,那麼你需要懂這項技術。如果你在處理極大的應用程式數據集,以至於你的程式常常達到記憶體的界限 ...
  • 介紹 的中文意思是易變的,是C++的一個關鍵字。它的作用就是允許修改被const修飾的對象的成員變數。 常用場景 什麼情況下我們會使用到mutable? 一般我們會用 修飾get類的函數,明確函數內部不會修改任何成員變數,但是如果內部的成員變數需要多線程讀寫,我們必須加鎖保證多線程安全。毫無疑問,加 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...