题目
题目描述 此时己是凌晨两点，刚刚做了 Codeforces 的小 A 掏出了英语试卷。英语作业其实不算多，一个小时刚好可以做完。然后是一个小时可以做完的数学作业，接下来是分别都是一个小时可以做完的化学，物理，语文……小 A 压力巨大。
这时小 A 碰见了一道非常恶心的数学题，给定了一个长度为 nn 的数列和若干个询问，每个询问是关于数列的区间表示数列的第 ll 个数到第 rr 个数)，首先你要统计该区间内大于等于 aa，小于等于 bb 的数的个数，其次是所有大于等于 aa，小于等于 bb 的，且在该区间中出现过的数值的个数。
小 A 望着那数万的数据规模几乎绝望，只能向大神您求救，请您帮帮他吧。
输入格式 第一行两个整数 n,mn,m
接下来 nn 个不超过 10^510 5 的正整数表示数列
接下来 mm 行，每行四个整数 l,r,a,bl,r,a,b，具体含义参见题意。
输出格式 输出 mm 行，分别对应每个询问，输出两个数，分别为在 ll 到 rr 这段区间中大小在 [a,b][a,b] 中的数的个数，以及大于等于 aa，小于等于 bb 的，且在该区间中出现过的数值的个数（具体可以参考样例）。
输入输出样例 输入 #1复制 3 4 1 2 2 1 2 1 3 1 2 1 1 1 3 1 3 2 3 2 3 输出 #1复制 2 2 1 1 3 2 2 1 说明/提示 N\leq 100000,M\leq 100000N≤100000,M≤100000，读入的数字均为 [1,10^5][1,10 5 ] 内的正整数。
思路
先离散化，然后记录一个pre[]数组表示每个数之前一次出现在哪里。于是本题的第二问就变成了这样一个问题：
输入(L,R,A,B)，输出有多少个x满足： L<=x<=R; A<=a[x]<=B; 0<=pre[x]<=L-1
于是就变成了3维数点，cdq完事
代码
#include<bits/stdc++.h>
#define maxn 100010
using namespace std
;
int n
,m
,a
[maxn
],b
[maxn
],h
[maxn
],ans
[maxn
],ans1
[maxn
],c
[maxn
];
struct qry
{int x
,y
,z
,f
,id
;};
vector
<qry
> v
,w
;
bool operator <=(qry a
,qry b
){
return pair(a
.y
,a
.z
)<=pair(b
.y
,b
.z
);
}
void ins(int p
,int v
){for(;p
<=n
;p
+=p
&-p
)c
[p
]+=v
;}
int Qry(int p
){int r
=0;for(;p
;p
&=p
-1)r
+=c
[p
];return r
;}
void CDQ(int l
,int r
){
if(l
+1>=r
)return;
int mid
=l
+r
>>1,i
=l
,j
=mid
,cnt
=0;
CDQ(l
,mid
),CDQ(mid
,r
);
w
.clear();
while(i
<mid
|| j
<r
)if(i
<mid
&& (j
==r
|| v
[i
]<=v
[j
])){
w
.push_back(v
[i
]);
if(!v
[i
].f
)ins(v
[i
].z
+1,1),cnt
++;
i
++;
}else{
w
.push_back(v
[j
]);
if(v
[j
].f
)
ans
[v
[j
].id
]+=v
[j
].f
*Qry(v
[j
].z
+1),
ans1
[v
[j
].id
]+=v
[j
].f
*cnt
;
j
++;
}
for(int i
=l
;i
<mid
;i
++)if(!v
[i
].f
)ins(v
[i
].z
+1,-1);
for(int i
=l
;i
<r
;i
++)v
[i
]=w
[i
-l
];
}
int main(){
scanf("%d%d",&n
,&m
);
for(int i
=1;i
<=n
;i
++)scanf("%d",a
+i
),b
[i
]=a
[i
];
sort(b
+1,b
+1+n
);
for(int i
=1;i
<=n
;i
++){
int pre
=h
[a
[i
]=lower_bound(b
+1,b
+1+n
,a
[i
])-b
];
h
[a
[i
]]=i
;
v
.push_back({i
,a
[i
],pre
,0,0});
}
for(int i
=1;i
<=m
;i
++){
int l
,r
,A
,B
;
scanf("%d%d%d%d",&l
,&r
,&A
,&B
);
A
=lower_bound(b
+1,b
+1+n
,A
)-b
;
B
=upper_bound(b
+1,b
+1+n
,B
)-b
-1;
v
.insert(v
.end(),{{r
,B
,l
-1,1,i
},{l
-1,A
-1,l
-1,1,i
},
{l
-1,B
,l
-1,-1,i
},{r
,A
-1,l
-1,-1,i
}});
}
stable_sort(v
.begin(),v
.end(),[](qry a
,qry b
){
return tuple(a
.x
,a
.y
,a
.z
)<tuple(b
.x
,b
.y
,b
.z
);
});
CDQ(0,v
.size());
for(int i
=1;i
<=m
;i
++)
printf("%d %d\n",ans1
[i
],ans
[i
]);
return 0;
}
