D1T3

冷不防 2023-08-17 15:45 144阅读 0赞

#include<bits/stdc++.h> using namespace std; const int N=500005; struct node{ int pos,val,id; bool operator <(const node &x)const{return x.pos>pos;} }; struct data{int l,r,pos;}q[N]; int n,m,a[N],ans[N],x,vis[N],p[N],c[N],l,r; double f[N],g[N]; std::vector<node> que; inline int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } inline double cal(int u,int v) {return a[u]+sqrt(abs(v-u))-a[v];} inline int find(data b,int u) { int ll=b.l,rr=b.r; while(ll<=rr) { int mid=(ll+rr)>>1; if(cal(b.pos,mid)>cal(u,mid))ll=mid+1; else rr=mid-1; } return ll; } inline void rev() {for(int i=1;i<=n/2;i++)swap(a[i],a[n-i+1]);} inline void solve(double *b) { int head=1,tail=0; for(int i=1;i<=n;i++) { q[head].l++; if(head<=tail&&q[head].r<q[head].l)head++; if(head>tail||cal(i,n)>cal(q[tail].pos,n)) { while(head<=tail&&cal(q[tail].pos,q[tail].l)<cal(i,q[tail].l)) tail--; if(head>tail)q[++tail]=data{i,n,i}; else { int ee=find(q[tail],i); q[tail].r=ee-1; q[++tail]=data{ee,n,i}; } } b[i]=cal(q[head].pos,i); } } inline int lowbit(int now){return (now&(-now));} inline void modify(int pos,int val) {for(int i=pos;i<=n;i+=lowbit(i))c[i]+=val;} inline int query(int pos) { int gg=0; for(int i=pos;i>=1;i-=lowbit(i))gg+=c[i]; return gg; } int main(int argc, char const *argv[]) { freopen("fight.in","r",stdin); freopen("fight.out","w",stdout); n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); solve(f);rev();solve(g); for(int i=1;i<=n;i++)p[i]=max(0,(int)ceil(max(f[i],g[n-i+1]))); for(int i=1;i<=m;i++) { x=read();l=read();r=read(); que.push_back(node{l-1,p[x]/2,i}); que.push_back(node{r,p[x]/2,i}); } sort(que.begin(),que.end()); int cur=1; for(int i=0;i<que.size();i++) { if(i)for(int j=que[i-1].pos+1;j<=que[i].pos;j++) modify(p[j],1); else for(int j=1;j<=que[i].pos;j++)modify(p[j],1); if(!vis[que[i].id]) {ans[que[i].id]-=query(que[i].val);vis[que[i].id]=true;} else ans[que[i].id]+=query(que[i].val); } for(int i=1;i<=m;i++)printf("%d\n",ans[i]); return 0; }

转载于:https://www.cnblogs.com/Ace-MYX/p/11306324.html