汕头市队赛SRM04 M题

M SRM 04

描述

给 n 个数 $A_{1..n}$ ，有 Q 个询问 [L,R]，每次求出有多少二元组 $(x,y)$ 同时满足 $L leq x < y leq R$ 和 $A_x geq A_y$

输入格式

第一行两个整数 n 和 Q

第二行 n 个整数 $A_{1..n}$

接下来 Q 行，每行代表一次询问，每行有两个整数为 L 和 R

输出格式

对于每次询问，依次输出其所得到的值

样例输入

样例输出

1
3

数据范围与约定

$1leq nleq 1000$
$1leq Qleq 100000$
$0 < A_i < 2^{32}$
有坑点，请仔细阅读题目

最近没什么图啊

就不放了

自己写的第一道莫队

看到这题后很激动

因为最近才写过类似的题（只比这个少了个等于号）

然而被坑点坑了

所以并没有什么卵用

坑点是输入不保证l<=r

一个诡异的坑点T^T

特判一波就a了

其实莫队的难点就是转移

只要把转移想出来了就没问题了

具体细节不讲了

如果不理解可以看一波bzoj3289: Mato的文件管理

然后再稍微推敲一下如何处理等于

#include<cstdio>  
#include<cmath>  
#include<cstring>  
#include<algorithm>  
const int N=100005,M=100005;  
struct node  
{  
    int order;
	long long v;  
}a[M];  
struct edgt  
{  
    int l,r,id;  
}q[N];  
int aa[M],c[N],pos[N];int n,m;long long now=0,ans[N];  
int lowbit(int i)  
{  
    return i&-i;  
}  
bool cmp(node a,node b){    return a.v<b.v;  }  
bool cmp2(edgt a,edgt b)  
{  
    if(pos[a.l]==pos[b.l])  return a.r<b.r;  
    return a.l<b.l;  
}  
void add(int x,int add)  
{  
    for(int i=x;i<=n;i+=lowbit(i))   c[i]+=add;  
}  
long long int qsum(int x)  
{  
    long long int sum=0;  
    for(int i=x;i>=1;i-=lowbit(i))   sum+=c[i];  
    return sum;  
}  
void solve()  
{  
    for(int i=1,l=1,r=0;i<=m;i++)  
    {  
        while(r<q[i].r)	  
        r++,add(aa[r],1),now+=r-l+1-qsum(aa[r]-1)-1;
        while(r>q[i].r)  
        add(aa[r],-1),now-=r-l-qsum(aa[r]-1),r--;
        while(l>q[i].l)  
        l--,add(aa[l],1),now+=qsum(aa[l])-1;
        while(l<q[i].l)  
        add(aa[l],-1),now-=qsum(aa[l]),l++;  
        ans[q[i].id]=now;  
    }  
}  
int main()  
{  
    int block;  
    scanf("%d",&n);block=sqrt(n);   scanf("%d",&m);  
    for(int i=1;i<=n;i++)    scanf("%lld",&a[i].v),a[i].order=i;  
    std::sort(a+1,a+1+n,cmp);  
    aa[a[1].order]=1;
    for(int i=2;i<=n;i++)   
	if(a[i].v==a[i-1].v)	aa[a[i].order]=aa[a[i-1].order];
	else aa[a[i].order]=i;
    
    for(int i=1;i<=m;i++)   
	{
		 scanf("%d %d",&q[i].l,&q[i].r);
		 if(q[i].l>n)q[i].l=n;
		 if(q[i].r>n)q[i].r=n;
		 if(q[i].l<1)q[i].l=1;
		 if(q[i].r<1)q[i].r=1;
		 q[i].id=i;  
	}
    for(int i=1;i<=n;i++)    pos[i]=(i-1)/block+1;  
    std::sort(q+1,q+1+m,cmp2);  
    solve();  
    for(int i=1;i<=m;i++)	if(q[i].l>q[i].r)	ans[q[i].id]=0;
    for(int i=1;i<=m;i++)    printf("%lld
",ans[i]);  
    
    return 0;  
}