codeforces 997E(线段树)

分析：

　　首先考虑如何计算整个数组有多少个good区间

　　容易发现一个区间是good区间当且仅当max-min-len=-1，且任意区间max-min-len>=-1

　　我们可以枚举右端点，然后维护前面每个位置到当前右端点的max-min-len值，容易发现我们只需要维护区间最小值和最小值的个数就行了，于是用线段树即可

　　于是我们可以得到以某个点为右端点的时候合法区间总数，那么我们把每次的结果加起来，就得到了整个数组有多少个good区间

　　每次右端点移动怎么更新呢？显然我们只需要用一个max单调栈，一个min单调栈来帮助寻找修改区间，容易知道修改区间的个数是O(n)级别的，所以整个修改是O(nlogn)的

　　好，现在我们回到原来的问题，如何求[l,r]内有多少个good区间

　　在这个问题中，我们实际上要额外知道“每个区间的历史答案和”，这是什么意思呢，比如说在i=7的时候，[4,7]里的答案存的是有多少个合法的位置是和7匹配的

　　但i=6的时候,[4,7]里的答案存的是有多少个合法的位置是和6匹配的

　　我们自然而然就考虑到把每个右端点时刻，一个区间的产生的答案值加起来就行了，但这个时间复杂度是巨大的

　　这里我们仍然可以用延迟标记来解决，比如右端点i枚举完了，我们可以给[1,i]上个tag，表示这整个区间的历史答案需要加上现在时刻的答案

　　时间复杂度O(nlogn)

 #include<bits/stdc++.h>

 using namespace std;

 #define mp make_pair

 const int maxn=;

 struct wjmzbmr

 {

     int mi,num,tag;

     int time;

     long long ans;

 }tree[maxn*+];

 vector<pair<int,int> > q[maxn+];

 long long ans[maxn+];

 int a[maxn+],s[maxn+],s1[maxn+];

 int len,len1;

 int n,m;

 void addtag(int k,int x)

 {

     tree[k].tag+=x;

     tree[k].mi+=x;

 }

 void addtime(int k,int x)

 {

     tree[k].time+=x;

     tree[k].ans+=1LL*x*tree[k].num;

 }

 void pushdown(int k)

 {

     if(tree[k].tag)

     {

         addtag(k*,tree[k].tag);

         addtag(k*+,tree[k].tag);

         tree[k].tag=;

     }

     if(tree[k].time)

     {

         if(tree[k].mi==tree[k*].mi) addtime(k*,tree[k].time);

         if(tree[k].mi==tree[k*+].mi) addtime(k*+,tree[k].time);

         tree[k].time=;

     }

 }

 void update(int k)

 {

     tree[k].mi=min(tree[k*].mi,tree[k*+].mi);

     tree[k].ans=tree[k*].ans+tree[k*+].ans;

     tree[k].num=;

     if(tree[k].mi==tree[k*].mi) tree[k].num+=tree[k*].num;

     if(tree[k].mi==tree[k*+].mi) tree[k].num+=tree[k*+].num;

 }

 void build(int k,int l,int r)

 {

     if(l>r) return;

     if(l==r)

     {

         tree[k].num=;

         tree[k].mi=-;

         return;

     }

     int mid=(l+r)>>;

     build(k*,l,mid);

     build(k*+,mid+,r);

     update(k);

 }

 void modify(int k,int l,int r,int ql,int qr,int x)

 {

     if(r<ql||l>qr||l>r) return;

     if(l>=ql&&r<=qr)

     {

         addtag(k,x);

         return;

     }

     if(l==r) return;

     pushdown(k);

     int mid=(l+r)>>;

     modify(k*,l,mid,ql,qr,x);

     modify(k*+,mid+,r,ql,qr,x);

     update(k);

 }

 void modify1(int k,int l,int r,int ql,int qr,int x)

 {

     if(r<ql||l>qr||l>r) return;

     if(l>=ql&&r<=qr)

     {

         if(tree[k].mi==-)

         addtime(k,x);

         return;

     }

     if(l==r) return;

     pushdown(k);

     int mid=(l+r)>>;

     modify1(k*,l,mid,ql,qr,x);

     modify1(k*+,mid+,r,ql,qr,x);

     update(k);

 }

 long long query(int k,int l,int r,int ql,int qr)

 {

     if(r<ql||l>qr||l>r) return ;

     if(l>=ql&&r<=qr) return tree[k].ans;

     if(l==r) return ;

     pushdown(k);

     int mid=(l+r)>>;

     long long ans=query(k*,l,mid,ql,qr)+query(k*+,mid+,r,ql,qr);

     update(k);

     return ans;

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;++i) scanf("%d",&a[i]);

     scanf("%d",&m);

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

     {

         int l,r;

         scanf("%d%d",&l,&r);

         q[r].push_back(mp(l,i));

     }

     build(,,n);

     for(int i=;i<=n;++i)

     {

         while(len&&a[s[len]]<a[i]) modify(,,n,s[len-]+,s[len],a[i]-a[s[len]]),--len;

         s[++len]=i;

         //for(int j=1;j<=len;++j) printf("%d ",a[s[j]]);printf("\n");

         while(len1&&a[s1[len1]]>a[i]) modify(,,n,s1[len1-]+,s1[len1],a[s1[len1]]-a[i]),--len1;

         s1[++len1]=i;

         //for(int j=1;j<=len1;++j) printf("%d ",a[s1[j]]);printf("\n");

         modify1(,,n,,i,);

         for(auto x:q[i]) ans[x.second]=query(,,n,x.first,i);

         //printf("%lld\n",query(1,1,n,1,i));

         //if(i==4) printf("%d\n",tree[2].ans);

         modify(,,n,,i,-);

     }

     for(int i=;i<=m;++i) printf("%lld\n",ans[i]);

     return ;

 }

巴特西

codeforces 997E(线段树)

最新文章

热门文章