題意：在數組中找到兩相等元素相距最大的距離且這兩元素間的元素都不小于該兩端值

思路：采用單調棧

例如：a[] = { 2 3 5 4 6 3 }，棧內存儲元素的坐標（從1開始），便于計算距離

1. 首先將a[1]、a[2]、a[3]依次入棧
2. 當到a[4]時，發現其小于棧頂元素（a[4] < a[stack.top()]），由于a[3]大于a[4]，這樣一來a[3]無論如何都不能與之后的元素相匹配，因為若是a[3]與a[i] (=5)匹配，但兩者之間一定會夾著小于它們的元素a[4]，因此不滿足條件將a[3]出棧，接著繼續檢查a[4]與棧頂元素的大小關系，直至a[4] >= stack.top()，否則便將棧頂出棧
3. 接著a[5]入棧，a[6]小于棧頂于是執行步驟2操作，最后到a[6] = a[stack.top()]，此時說明可以匹配兩者，記錄a[6]和a[2]的坐標差，保留a[2]在棧中而a[6]不入棧，因為目前a[2]右側的元素均不小于它，即a[2]還有機會被匹配，且a[2]更靠左這樣計算出的結果也會最大化

#include<bits/stdc++.h>
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0)
const int N = (int)1e6+10;
using namespace std;
stack<int> st;
int a[N];
int main()
{fastio();int n;cin >> n;int ans = 0;for (int i = 1; i <= n; i++){cin >> a[i];if (st.empty() || a[i] > a[st.top()]){st.push(i);}else{while (!st.empty() && a[i] < a[st.top()]) st.pop();if (st.empty()) st.push(i);else if (a[i] == a[st.top()]){ans = max(ans, i - st.top());}else if (a[i] > a[st.top()]){st.push(i);}}}cout << ans << "\n";return 0;
}

題意：對于一個整型數組a，每次詢問$[L,R]$之間為x的倍數的元素的個數

數據范圍：數組長度 $n:[0,10^5]$ ，詢問次數 $q:[0,5?10^4]$，因數$x:[1,10^5]$

思路：思考若采用暴力，時間復雜度為$O(n?q)$，$10^9$的數量級顯然會超時，因此對這種多次詢問的問題不妨采用分塊的思想，將每$\sqrt{n}$個元素作為一塊，因此數組大致可分為$\sqrt{n}$塊（數組末尾有時不能組成完整的一塊），分塊后首先進行預處理，記錄每塊內對于因數$x:[1,10^5]$詢問對應該塊內元素的結果個數（枚舉塊內元素a[i]，找出a[i]所有的因數，時間復雜度為$O(\sqrt{a_i})$），因此預處理的總時間復雜度為$O(n?\sqrt{a_i})$。此后對于一次詢問，較一般的情況是$[L,H)+[H,T)+[T,R]$，其中$[L,H)$和$[T,R]$屬于某一塊一部分，因此對于這兩部分采取暴力求解，而$[H,T)$則屬于多個連續的完整的塊，可以直接利用預處理的結果，其他的詢問情況討論分析即可，全部詢問的時間復雜度為$O(q?(\sqrt{n}+2\sqrt{n}))$也即$O(q?\sqrt{n})$，其中的$2\sqrt{n}$理解為暴力求解的部分

下面貼的是標程，自己第一次寫的分塊有點不堪入目

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int sum[320][maxn];
int arr[maxn];
int n, q;
void blocked() {int sz = sqrt(n);for (int i = 0; i < n; ++i) {for (int j = 1; j * j <= arr[i]; ++j) {if (arr[i] % j == 0) {sum[i / sz][j]++;if (arr[i] / j != j) sum[i / sz][arr[i] / j]++;}}}
}
int qurey(int l, int r, int x) {int sz = sqrt(n);int ans = 0;for (int i = l; i <= r && i / sz == l / sz; ++i) {if (arr[i] % x == 0) ans++;}if (l / sz == r / sz) return ans;for (int i = r / sz * sz; i <= r; ++i) {if (arr[i] % x == 0) ans++;}for (int j = l / sz + 1; j <= r / sz - 1; ++j) {ans += sum[j][x];}return ans;
}
int main() {while (~scanf("%d%d", &n, &q)) {memset(sum, 0, sizeof(sum));for (int i = 0; i < n; ++i) {scanf("%d", arr + i);}blocked();while (q--) {int l, r, x;scanf("%d%d%d", &l, &r, &x);l--, r--;printf("%d\n", qurey(l, r, x));}}return 0;
}

自己的代碼：

#include<bits/stdc++.h>
#define debug1(x) cout<<#x<<":"<<x<<endl
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
typedef unsigned long long ull;
const int N = 100010;
using namespace std;
int a[N];
int mp[320][N];
void Factor(int i,int block_no)
{int j = 1;for(; j * j < a[i]; j++){if(a[i] % j == 0){mp[block_no][j]++;mp[block_no][a[i] / j]++;}}if(j * j == a[i]) mp[block_no][j]++;
}
int main()
{int n,q;cin>>n>>q;for(int i = 0; i < n; i++) scanf("%d",&a[i]);int block_size = sqrt(n);int block_no_max;for(int i = 0; (i + 1) * block_size - 1 < n; i++){for(int j = i * block_size; j < (i + 1) * block_size; j++){Factor(j,i);}block_no_max = i;}while(q--){int ans = 0;int l,r,x;scanf("%d%d%d",&l,&r,&x);l--;r--;int head = l / block_size;int tail = r / block_size;if(head == tail){if(r - l + 1 == block_size) ans += mp[head][x];else{for(int i = l; i <= r; i++){if(a[i] % x == 0) ans++;}}printf("%d\n",ans);continue;}if(l % block_size){for(int i = l; i < (head + 1) * block_size; i++){if(a[i] % x == 0) ans++;}head++;}if((r + 1) % block_size){for(int i = tail * block_size; i <= r; i++){if(a[i] % x == 0) ans++;}tail--;}for(int i = head; i <= tail; i++){ans += mp[i][x];}printf("%d\n",ans);}return 0;
}