题目：P4396 [AHOI2013]作业
思路：
方法一：
暴力
显然跑不过去
用莫队优化一下就过了
具体有两种写法：
- 开值域树状数组维护第一问，用计数桶+值域树状数组维护第二问。每次移动和查询复杂度都是(O(logn))，总复杂度(O(nsqrt n logn))，复杂度有点高，但这题时限宽，可以过。
- 莫队的特点是修改多、查询少，与分块吻合。于是对值域分块开桶，每次移动指针(O(1))，查询(O(sqrt n))，总复杂度(O(nsqrt n))。
粘一下以前的代码：
Code：
#include <bits/stdc++.h>
using namespace std;
const int N = 100005, T = 350;
#define blo(x) (((x) - 1) / len + 1)
#define bl(x) (((x) - 1) * len + 1)
#define br(x) (min((x) * len , n))
int n, m, len, ans1, ans2, cnt[N], v[N], sum1[T], sum2[N], res1[N], res2[N];
struct Q {
int l, r, a, b, block, id;
} q[N];
inline void read(int &tmp) {
register char c = getchar();
for(tmp = 0; !isdigit(c); c = getchar());
for(; isdigit(c); tmp = tmp * 10 + c - 48, c = getchar());
}
inline bool cmp(const Q &a, const Q &b) {
return (a.block ^ b.block) ? a.block < b.block : (a.block & 1) ? a.r <b.r : a.r>b.r ;
}
inline void add(int p) {
if(!cnt[v[p]]++) ++sum2[blo(v[p])];
++sum1[blo(v[p])];
}
inline void del(int p) {
if(!--cnt[v[p]]) --sum2[blo(v[p])];
--sum1[blo(v[p])];
}
void ask(int L, int R) {
int p = blo(L), q = blo(R);
ans1 = ans2 = 0;
if(q - p < 2) {
for(int i = L; i <= R; ++i) ans1 += cnt[i], ans2 += (cnt[i] > 0);
return;
}
for(int i = p + 1; i <= q - 1; ++i) ans1 += sum1[i], ans2 += sum2[i];
for(int i = L, limit = br(p); i <= limit; ++i) ans1 += cnt[i], ans2 += (cnt[i] > 0);
for(int i = bl(q); i <= R; ++i) ans1 += cnt[i], ans2 += (cnt[i] > 0);
return;
}
int main() {
read(n);
read(m);
len = ceil(pow(n * 1.0, 0.5));
for(int i = 1; i <= n; ++i) read(v[i]);
for(int i = 1; i <= m; ++i) {
read(q[i].l);
read(q[i].r);
read(q[i].a);
read(q[i].b);
q[i].block = blo(q[i].l);
q[i].id = i;
}
sort(q + 1, q + 1 + m, cmp);
int l = q[1].l , r = l - 1, ql, qr;
for(int i = 1; i <= m; ++i) {
ql = q[i].l ;
qr = q[i].r ;
while(l < ql) del(l++);
while(l > ql) add(--l);
while(r < qr) add(++r);
while(r > qr) del(r--);
ask(q[i].a, q[i].b);
res1[q[i].id] = ans1;
res2[q[i].id] = ans2;
}
for(int i = 1; i <= m; ++i) printf("%d %d
", res1[i], res2[i]);
return 0;
}
方法二：
注意到第一问是裸的二维数点，第二问类似P1972 [SDOI2009]HH的项链，可以转化成三维数点。
(Lleq ileq R\a leq val[i] leq b\pre[i]leq L-1)
(pre[i])为(val[i])上一次出现的位置。
静态二维数点是二维偏序，树状数组+扫描线/cdq（离线）、主席树（在线）什么的都可以。
静态三维数点是三维偏序，可以cdq（离线）或树套树（在线）。
我很菜，没写过树套树，就写了离线算法。
第一问的二维偏序和第二问的前两维一样，可以顺便cdq统计。
cdq只能处理一个不等号，所以前两维要容斥（前缀和）拆成四个询问，数组大小要开够。
复杂度(O(nlog^2n))。
因为常数有点大，用时和莫队差不多...
Code
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=1e6+5,T=5e6+5;
int n,m,tot,pre[N],res1[M],res2[M];
struct data{
int type,x,y,z,id;
inline data(int type=0,int x=0,int y=0,int z=0,int id=0):type(type),x(x),y(y),z(z),id(id){}
inline bool operator < (const data &b)const{
return y^b.y?y<b.y:type<b.type;
}
}a[T],b[T];
struct BIT{
int tim,vis[N],c[N];
inline void add(int pos){
for(++pos;pos<=n+1;pos+=pos&-pos){
if(vis[pos]!=tim) vis[pos]=tim,c[pos]=1;
else ++c[pos];
}
}
inline int query(int pos){
int res=0;
for(++pos;pos;pos^=pos&-pos) if(vis[pos]==tim) res+=c[pos];
return res;
}
}tree;
inline bool cmp(const data &a,const data &b){
return a.x^b.x?a.x<b.x:a.type<b.type;
}
void cdq(int l,int r){
if(l==r) return;
int mid=(l+r)>>1,tl=l,tr=mid+1,cnt=0;
cdq(l,mid);
cdq(mid+1,r);
++tree.tim;
for(int i=l;i<=r;++i){
if((tl<=mid&&a[tl]<a[tr])||tr>r){
if(a[tl].type==1) ++cnt,tree.add(a[tl].z);
b[i]=a[tl++];
}
else{
if(a[tr].type==2) res1[a[tr].id]-=cnt,res2[a[tr].id]-=tree.query(a[tr].z);
if(a[tr].type==3) res1[a[tr].id]+=cnt,res2[a[tr].id]+=tree.query(a[tr].z);
b[i]=a[tr++];
}
}
for(int i=l;i<=r;++i) a[i]=b[i];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,val;i<=n;++i){
scanf("%d",&val);
a[++tot]=data(1,i,val,pre[val],0);
pre[val]=i;
}
for(int i=1,l,r,A,B;i<=m;++i){
scanf("%d%d%d%d",&l,&r,&A,&B);
a[++tot]=data(2,l-1,B,l-1,i);
a[++tot]=data(2,r,A-1,l-1,i);
a[++tot]=data(3,l-1,A-1,l-1,i);
a[++tot]=data(3,r,B,l-1,i);
}
sort(a+1,a+1+tot,cmp);
cdq(1,tot);
for(int i=1;i<=m;++i) printf("%d %d
",res1[i],res2[i]);
return 0;
}