饮水计划（ST表+二分+差分）

1008 饮水计划

思路：看数据范围肯定是需要预处理出每个区间的k的个数。遍历每个区间[i，j],k=j，求出[i，j]的最大值mx，再二分求出[j+1,n]中满足[j+1,mid]的最小值>=mx，并且mid要尽可能大（区间最值可以用st表来求，时间复杂度O（1）），然后求得区间[i,j+1]~[i,mid]的k的个数要加1，可以用差分来算，然后求前缀和就行了。

这道题会卡“endl”换成 '\n'  就行了

Code:

int n,m;struct STList{vector<vector<int>> stmax,stmin;void init(vector<int> &a){int len=a.size();int k=__lg(len)+1;stmax.assign(len,vector<int>(k));stmin.assign(len,vector<int>(k));for(int i=1;i<len;i++){stmax[i][0]=a[i];stmin[i][0]=a[i];}for(int i=1;i<k;i++)for(int j=1;j+(1<<i)-1<len;j++){stmax[j][i]=max(stmax[j][i-1],stmax[j+(1<<(i-1))][i-1]);stmin[j][i]=min(stmin[j][i-1],stmin[j+(1<<(i-1))][i-1]);}} int Max(int l,int r){int k=__lg(r-l+1);return max(stmax[l][k],stmax[r-(1<<k)+1][k]);}int Min(int l,int r){int k=__lg(r-l+1);return min(stmin[l][k],stmin[r-(1<<k)+1][k]);}};
void solve()
{cin>>n>>m;vector<int> a(n+1);for(int i=1;i<=n;i++) cin>>a[i];STList st; st.init(a);vector<vector<int>> f(n+1,vector<int>(n+1,0));for(int i=1;i<n;i++){for(int j=i+1;j<=n;j++){int L=j,R=n;int maxx=st.Max(i,j-1);while(L<R){int mid=(L+R+1)>>1;if(st.Min(j,mid)>=maxx) L=mid;else R=mid-1;}if(st.Min(j,L)>=maxx){f[i][j]++;f[i][L+1]--;}f[i][j]+=f[i][j-1];}}while(m--){int l,r;cin>>l>>r;cout<<f[l][r]<<endl;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;//t=1;while(t--) solve();
}