\(GZOI2017D1T3\)
题目链接? 不存在的
题面
首先, 对于一个 \(a_x\), 满足条件的 \(a_y\) 一定是和它差值最小的那一个.
因为 \(a_i\) 互不相同, 那么满足条件的 \(a_y\) 最多只有 \(2\) 个, 我们可以预处理出所有好的配对.
那么问题就变成了求区间内配对的数量, 这就是个经典问题了.
对询问按左端点从大到小排序, 扫描一遍, 设当前询问为 \([l,r]\), 每次加入所有 \(l\le x\) 的配对, 查询有多少配对满足 \(y\le r\)
可以使用树状数组实现.
时间复杂度 \(O((n+m)\log n)\)
空间复杂度 \(O(n+m)\)
代码:
- #include
- #include
- #include
- #include
- #include
- typedef long long ll;
- inline int Min(const int a,const int b){return a<b?a:b;}
- inline int Max(const int a,const int b){return a>b?a:b;}
- #define Getchar (p1==p2&&(p2=(p1=In)+fread(In,1,1<<22,stdin),p1==p2)?EOF:*p1++)
- char In[1<<22],*p1=In,*p2=In,Ch;
- inline int Getint(int x=0)
- {
- while(!isdigit(Ch=Getchar));
- for(;isdigit(Ch);Ch=Getchar)x=x*10+(Ch^48);
- return x;
- }
- const int N=300005,Inf=0x3f3f3f3f;
- int n,m,c[N],Ans[N];
- struct Pair{int a,p;inline bool operator<(const Pair &o)const{return a<o.a;}}a[N];
- std::vector Ms[N],Q1[N],Q2[N];// 贡献, 询问右端点, 询问 ID
- inline void Insert(int x,int y){Ms[Min(x,y)].push_back(Max(x,y));}
- void Modify(int x){for(;x<=n;x+=x&-x)++c[x];}
- int Query(int x,int s=0){for(;x;x^=x&-x)s+=c[x];return s;}
- int main()
- {
- n=Getint(),m=Getint();
- for(int i=1;i<=n;++i)a[i]=(Pair){Getint(),i};
- std::sort(a+1,a+n+1);
- for(int i=1;i<=n;++i)
- {
- int Md=Inf;
- if(i!=1)Md=Min(Md,a[i].a-a[i-1].a);
- if(i!=n)Md=Min(Md,a[i+1].a-a[i].a);
- if(i!=1&&a[i].a-a[i-1].a==Md)Insert(a[i].p,a[i-1].p);
- if(i!=n&&a[i+1].a-a[i].a==Md)Insert(a[i].p,a[i+1].p);
- }
- for(int i=1,l;i<=m;++i)l=Getint(),Q1[l].push_back(Getint()),Q2[l].push_back(i);
- for(int i=n;i>=1;--i)
- {
- for(int j=0;j<(int)Ms[i].size();++j)Modify(Ms[i][j]);
- for(int j=0;j<(int)Q1[i].size();++j)Ans[Q2[i][j]]=Query(Q1[i][j]);
- }
- ll Sum=0;
- for(int i=1;i<=m;++i)Sum+=(ll)Ans[i]*i;
- printf("%lld\n",Sum);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3296346.html