洛谷P3987 我永遠喜歡珂朵莉

2022-09-23 02:21:53 字數 1980 閱讀 7781

給珂朵莉一個長為 \(n\) 的非負數序列 \(a\),支援以下兩個操作:

珂朵莉很可愛,所以你要幫珂朵莉寫這個題。

\(1\leq n,m\leq 100000,0\leq ai\leq 500000,1 \leq x\leq 500000\)

想找一道平衡樹的練習碼力(大概?)的題寫寫,然後就翻到了這題。

首先,在 \([1,500000]\) 的範圍內,一個數最多有 \(200\) 個因子。

所以我們可以開 \(500000\) 棵平衡樹,第 \(i\) 棵儲存是 \(i\) 的倍數的數字的下標。這樣平衡樹最大隻用開到 \(200n\)。

然後我們再開一個樹狀陣列,用於求區間和。注意儘量不要用線段樹,常數大。

對於一個修改操作1 l r x,我們在第 \(x\) 棵平衡樹中 \(dfs\),找到每一個位於 \([l,r]\) 的數字。然後在樹狀陣列中找到這個數\(p\),將它變成 \(\frac\)。

如果此時 \(\frac\) 依然是 \(x\) 的倍數,那麼將這個點保留在平衡樹中不變,否則我們將這個點插入到棧中,最後將棧中的所有位置從第 \(x\) 棵平衡樹中刪除。

這樣就簡單的解決了這道題,顯然每個數最多被除 \(\log\) 次(忽略除以 1 的情況),所以時間複雜度為 \(o(n\sqrt\log n+nd\log n)\),不夠優秀。

吸氧。treap是一棵笛卡爾樹,所以我們可以在求出每一個數字的因數後,用一個 \(\operatorname\) 儲存一個數 \(x\) 的倍數的下標。然後 \(o(n)\) 建樹。時間複雜度\(o(n\sqrt+nd\log n)\)。

我們其實不需要 500000 棵平衡樹,只要將所有詢問到的數字建平衡樹即可。這樣平衡樹就從 500000 棵變成了 100000 棵。建樹的複雜度也會減小。

換換隨機種子(假)。

#pragma gcc optimize("ofast","inline")

#include #include #include #include #include #include #define reg register

using namespace std;

typedef long long ll;

const int n=100010,m=500010,d=200,inf=1e9;

int n,m,totel,a[n],rt[m],q[n],opt[n],l[n],r[n],x[n],y[n];

vectorqdel,fac[m];

inline int read()

inline void write(ll x)

struct bit

inline ll query(int x)

}bit;

struct treap

inline int build(int l,int r)

inline void zig(int &x)

inline void zag(int &x)

inline void ins(int &x,int v)

else

}inline void del(int &x,int v)

else x=0;

} else if (v1) fac[a[i]].push_back(i);

}inline void dfs(int x,int l,int r,int q)

}int main()

for (reg int i=1;i<=m;i++)

sort(y+1,y+1+totel);

totel=unique(y+1,y+1+totel)-y-1;

for (reg int i=1;i<=totel;i++)

for (reg int i=1;i<=m;i++)

else write(bit.query(r[i])-bit.query(l[i]-1)),putchar(10);

} return 0;

}