有一個任意兩數不同且長度為 \(n\) 的序列 \(a\)，對它有 \(q\) 個資訊，形如 \(a_l, a_{l+1},\cdots,a_r\) 的最小值是 \(r\) .
問是否產生矛盾？
矛盾分兩類：
- 如果兩個區間的最小值一樣，但是這兩個區間沒有交集（每個數各不相同）
- 如果幾個比較大的區間的并集包含了一些比較小的區間的交集
后面這個就是相當于讓搞一個資料結構，能維護
- 合并區間
- 問區間包含關系
合并區間可以暴力并查集把每個 \([l,r]\) 內的 father 都鏈到 \(r\) 上，復雜度其實挺低（并查集的魔法均攤qwq）
代碼大概這樣
using namespace std;
const int N = 1e6+500, Q = 25555, I = 0x3f3f3f3f;
inline void chkmin(int& a, int b){if (a > b) a = b;}
inline void chkmax(int& a, int b){if (a < b) a = b;}
struct Input
{
int l, r, v;
bool operator < (const Input& x)const{return v > x.v;}
}inp[Q], t[Q];
int n, q;
struct Magic
{
int fa[N]; // dsu
void init(){for (int i=0; i<=n+3; i++) fa[i] = i;}
void clear(){init();}
int get(int x){return fa[x] == x ? x : fa[x] = get(fa[x]);}
void merge(int l, int r)
{
for (int u = l; u <= r; u++)
fa[get(u)] = get(r+1); // dsu union
}
bool crs(int l, int r){return get(l) > r;}
Magic(){init();}
}T;
bool check(int r) // -> is NOT true
{
T.clear();
for (int i=1; i<=r; i++) t[i] = inp[i];
sort(t+1, t+1+r);
int lmin, lmax, rmin, rmax;
lmin = lmax = t[1].l; rmin = rmax = t[1].r;
for (int i=2; i<=r; i++)
{
if (t[i].v == t[i-1].v) // Case 1
{
lmin = min(lmin, t[i].l); lmax = max(lmax, t[i].l);
rmin = min(rmin, t[i].r); rmax = max(rmax, t[i].r);
if (rmin < lmax) return true;
continue;
} // Case 2
if (T.crs(lmax, rmin)) return true;
T.merge(lmin, rmax);
lmin = lmax = t[i].l; rmin = rmax = t[i].r;
}
return T.crs(lmax, rmin);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/385274.html
標籤：其他