admin 管理员组文章数量: 1184232
Minimum ,Maxinum (单调栈，区间贡献处理细节）
思路
给定数组a，求满足条件的区间数
- 区间中的最大值是最小值的倍数
constrains:
1 ≤ n ≤ 1 0 5 1\leq n\leq 10^5 1≤n≤105
思路
先单调栈处理出 l e s s l , l e s s r less_l,less_r lessl,lessr左右第一个小， g e l , g e r ge_l,ge_r gel,ger左右第一个大，有一个细节， g e r ge_r ger必须大于a[i]自身。
首先 d i [ j ] di[j] di[j]处理出 j j j的所有因数 O ( A l o g A ) O(AlogA) O(AlogA)。
我们考虑枚举最大值的贡献，假设当前最大值为 a [ i ] a[i] a[i]，枚举他的因数 j = d i [ a [ i ] ] j = di[a[i]] j=di[a[i]]，维护i左边第一个 j 1 j_1 j1和右边第一个 j 2 j_2 j2，可以用双指针实现，两者必须在 ( g e l [ i ] , g e r [ i ] ) (ge_l[i],ge_r[i]) (gel[i],ger[i]) 才有贡献，那么 j 1 j_1 j1的贡献为 ( l e s s l [ j 1 ] , l e s s r [ j 2 ] ) (less_{l}[j_1],less_{r}[j_2]) (lessl[j1],lessr[j2])和i的区间的交集的 j 1 j_1 j1的左开右闭和 i 的左闭右开 i的左闭右开 i的左闭右开，开闭必须想清楚， j 2 j_2 j2要避免重复贡献（因为 l e s s l [ j 2 ] less_l[j_2] lessl[j2]包含了 j 1 j_1 j1）。 g e r ge_r ger大于自身，使得 i i i不会重复贡献（非常像逆序对的贡献方式，卡掉某一个方向的贡献就能避免重复，但要想清楚不容易）。
代码
#include<bits/stdc++.h>
using namespace std;
#define pow2(X) (1ll<<(X))
#define SIZE(A) ((int)A.size())
#define LENGTH(A) ((int)A.length())
#define ALL(A) A.begin(),A.end()
#define F(i,a,b) for(ll i=a;i<=(b);++i)
#define dF(i,a,b) for(ll i=a;i>=(b);--i)
#define GETPOS(c,x) (lower_bound(ALL(c),x)-c.begin())
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define pb push_back
#define pr pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define eps 1e-6
#define PI acos(-1.0)
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ipair;
typedef vector<int> VI;
typedef vector<long long> VLL;
typedef vector<vector<long long > > VVLL;
typedef vector<vector<int> > VVI;
typedef vector<double> VD;
typedef vector<string> VS;
//const int mods = 998244353;
const int mods = 1e9+7;
const int maxn = 5e5+10;
const int N = 5e5+10;
const int E = 1e4+10;
const int lim = 1e6+10;
ll qpow(ll a,ll b) {ll res=1;a%=mods; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mods;a=a*a%mods;}return res;}
ll lcm(ll a, ll b) {return a / __gcd(a, b) * b;}
int read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}/***********************************
learning time
u=*max_element(a.begin(),a.end())
***********************************/ll n,m,k;
int a[maxn];
int less_l[maxn],less_r[maxn],ge_l[maxn],ge_r[maxn],ind[lim];
vector<int> di[lim];
vector<int> pos[lim];int main(){// freopen("C:\\Users\\Gao\\Desktop\\validation_input\\watering_well_chapter_2_input.txt","r",stdin);// freopen("C:\\Users\\Gao\\Desktop\\validation_input\\output.txt","w",stdout);ios_base::sync_with_stdio(0);F(i,1,lim-10){for(int j = i;j<=lim-10;j+=i){di[j].pb(i);}}int T;cin>>T; //T = 1;F(turn,1,T){cin>>n;F(i,1,n){cin>>a[i];pos[a[i]].pb(i);}{stack<int> s;F(i,1,n){while(!s.empty()&&a[s.top()]>=a[i]) s.pop();less_l[i] = (s.empty()?0:s.top());s.push(i);}}{stack<int> s;dF(i,n,1){while(!s.empty()&&a[s.top()]>=a[i]) s.pop();less_r[i] = (s.empty()?n+1:s.top());s.push(i);}}{stack<int> s;F(i,1,n){while(!s.empty()&&a[s.top()]<a[i]) s.pop();ge_l[i] = (s.empty()?0:s.top());s.push(i);}}{stack<int> s;dF(i,n,1){while(!s.empty()&&a[s.top()]<=a[i]) s.pop();ge_r[i] = (s.empty()?n+1:s.top());s.push(i);}}ll ans = 0;F(i,1,n){for(auto j:di[a[i]]){ //pos[j] must be before and after maa,so O(n) push it go//while(ind[j]<pos[j].size()&&pos[j][ind[j]]<i) ind[j]++;if(ind[j]>0){int p = pos[j][ind[j]-1];if(i<less_r[p]&&p>ge_l[i]){int rig = min(less_r[p],ge_r[i]);int lef = max(less_l[p],ge_l[i]);ans += 1ll*(rig-i)*(p-lef);} }if(ind[j]<pos[j].size()){int p = pos[j][ind[j]];if(i>less_l[p]&&p<ge_r[i]){int rig = min(less_r[p],ge_r[i]);int lef = max({less_l[p],ge_l[i],ind[j]>=1?pos[j][ind[j]-1]:-1});ans += 1ll*(rig-p)*(i-lef);}}}ind[a[i]]++;//保证a[i]恒在下一个maa的后面（或重叠）}cout<<ans<<endl;F(i,1,n){for(auto j:di[a[i]]){ind[j] = 0;pos[j].clear();}less_l[i]=less_r[i]=ge_l[i]=ge_r[i]=0;}}
}/**/
本文标签： minimum Maxinum (单调栈，区间贡献处理细节）
版权声明：本文标题：Minimum ,Maxinum (单调栈，区间贡献处理细节） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1699596064a364431.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论