首页 > 代码库 > Codeforces 526F Pudding Monsters
Codeforces 526F Pudding Monsters
先把题目抽象一下:
有一个静态的数组,求有多少个区间[i,j]满足:j-i==max{ai,...,aj}-min{ai,...,aj}
也就是要求max-min+i-j==0的区间数
所以肿么做呢?
首先枚举i(这里倒着做,比较好理解),维护以i为开头的所有区间
相当于每次要在一坨区间的最前面同时加一个元素(并且增加一个仅含有ai的区间[i,i])
然后很惊喜的发现实际上对于这一坨区间的权值(max-min+i-j)只有以下几个操作:
1.同时-1,因为i减小了1
2.改max(这个一定只有有限段进行区间加减的操作)
3.改min(同理)
维护最大最小两个单调队列,每个元素(注意不是每次)出队的同时把它本来“管辖”的区域区间修改一下
这样就只需要一个兹磁区间修改兹磁查区间最小值及其出现次数的线段树即可
果断标记永久化(好写好想常数还小)
1 #include <bits/stdc++.h> 2 #define mid (l+r>>1) 3 using namespace std; 4 long long dep,ret,n,p,debug; 5 int Min[2400001],flag[2400001],num[2400001]; 6 int posa[600001],posb[600001],a[600001],b[600001],s[600001]; 7 void add(int now,int l,int r,int x,int y,long long z) 8 { 9 if(l==x && r==y) 10 { 11 Min[now]+=z; 12 flag[now]+=z; 13 return; 14 } 15 if(x<=mid) add(now<<1,l,mid,x,min(y,mid),z); 16 if(y>mid) add(now<<1|1,mid+1,r,max(x,mid+1),y,z); 17 if(Min[now<<1]==Min[now<<1|1]) 18 Min[now]=Min[now<<1]+flag[now],num[now]=num[now<<1]+num[now<<1|1]; 19 else 20 { 21 int t; 22 if(Min[now<<1]<Min[now<<1|1]) t=now<<1; 23 else t=now<<1|1; 24 Min[now]=Min[t]+flag[now]; 25 num[now]=num[t]; 26 } 27 } 28 void query(int now,int l,int r,int x,int y) 29 { 30 if(l==x && r==y) 31 { 32 if(Min[now]+dep==0) 33 ret+=num[now]; 34 return; 35 } 36 dep+=flag[now]; 37 if(x<=mid) query(now<<1,l,mid,x,min(y,mid)); 38 if(y>mid) query(now<<1|1,mid+1,r,max(x,mid+1),y); 39 } 40 void build(int now,int l,int r) 41 { 42 if(l==r) 43 { 44 Min[now]=0; 45 num[now]=1; 46 return; 47 } 48 build(now<<1,l,mid); 49 build(now<<1|1,mid+1,r); 50 Min[now]=0; 51 num[now]=r-l+1; 52 } 53 int main() 54 { 55 scanf("%d",&n); 56 build(1,1,n); 57 for(int i=1;i<=n;i++) 58 scanf("%d",&p),scanf("%d",&s[p]); 59 int la=0,lb=0; 60 posa[0]=n+1;posb[0]=n+1; 61 for(int i=n;i>=1;i--) 62 { 63 while(la && a[la]<=s[i]) 64 { 65 add(1,1,n,posa[la],posa[la-1]-1,s[i]-a[la]); 66 --la; 67 } 68 while(lb && b[lb]>=s[i]) 69 { 70 add(1,1,n,posb[lb],posb[lb-1]-1,b[lb]-s[i]); 71 --lb; 72 } 73 ++la;++lb; 74 a[la]=s[i];posa[la]=i; 75 b[lb]=s[i];posb[lb]=i; 76 dep=0; 77 query(1,1,n,i,n); 78 add(1,1,n,i,n,-1); 79 } 80 printf("%lld\n",ret); 81 return 0; 82 }
Codeforces 526F Pudding Monsters
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。