题目描述
此时己是凌晨两点，刚刚做了 Codeforces 的小 A 掏出了英语试卷。英语作业其实不算多，一个小时刚好可以做完。然后是一个小时可以做完的数学作业，接下来是分别都是一个小时可以做完的化学，物理，语文…小A压力巨大。
这是小 A 碰见了一道非常恶心的数学题，给定了一个长度为
n
n
n 的数列和若干个询问，每个询问是关于数列的区间
[
l
,
r
]
[l,r]
[l,r]（表示数列的第
l
l
l 个数到第
r
r
r 个数），首先你要统计该区间内大于等于
a
a
a，小于等于
b
b
b 的数的个数，其次是所有大于等于
a
a
a，小于等于
b
b
b 的，且在该区间中出现过的数值的个数。
小 A 望着那数万的数据规模几乎绝望，只能向大神您求救，请您帮帮他吧。
N
=
100000
N=100000
N=100000，
M
=
1000000
M=1000000
M=1000000。
算法分析
莫队算法+分块，和 Gty的二逼妹子序列 差不多，是那个题的简单增强版。
BZOJ 上过了，LG 上 RE 了两个点，不改了。(╯‵□′)╯︵┻━┻
代码实现
#include <cstdio>
#include <cmath>
#include <algorithm>
#define cmin(x,y) x=std::min(x,y)
#define cmax(x,y) x=std::max(x,y)
const int maxn
=100005;
const int maxm
=1000005;
struct ask
{int id
,l
,r
,a
,b
;} qs
[maxm
];
int sz
,bl
[maxn
],le
[maxn
],ri
[maxn
];
inline bool cmp(const ask
&x
,const ask
&y
) {return bl
[x
.l
]^bl
[y
.l
]?x
.l
<y
.l
:bl
[x
.l
]&1?x
.r
<y
.r
:x
.r
>y
.r
;}
int a
[maxn
],cnt
[maxn
],num
[maxn
],sum
[maxn
],ans1
[maxm
],ans2
[maxm
];
int main() {
int n
,m
;scanf("%d%d",&n
,&m
);
for(register int i
=1;i
<=n
;++i
) scanf("%d",&a
[i
]);
for(register int i
=0;i
<m
;++i
) {qs
[i
].id
=i
;scanf("%d%d%d%d",&qs
[i
].l
,&qs
[i
].r
,&qs
[i
].a
,&qs
[i
].b
);}
sz
=n
/sqrt(m
*2/3);for(register int i
=1;i
<=n
;++i
) {bl
[i
]=(i
-1)/sz
+1;le
[i
]=n
;ri
[i
]=0;}
std
::sort(qs
,qs
+m
,cmp
);
for(register int i
=1;i
<=n
;++i
) {cmin(le
[bl
[i
]],i
);cmax(ri
[bl
[i
]],i
);}
for(register int i
=0,l
=1,r
=0;i
<m
;++i
) {
while(l
<qs
[i
].l
) {
--cnt
[a
[l
]];--sum
[bl
[a
[l
]]];
if(!cnt
[a
[l
]]) --num
[bl
[a
[l
]]];
++l
;
}
while(l
>qs
[i
].l
) {
--l
;
if(!cnt
[a
[l
]]) ++num
[bl
[a
[l
]]];
++cnt
[a
[l
]];++sum
[bl
[a
[l
]]];
}
while(r
<qs
[i
].r
) {
++r
;
if(!cnt
[a
[r
]]) ++num
[bl
[a
[r
]]];
++cnt
[a
[r
]];++sum
[bl
[a
[r
]]];
}
while(r
>qs
[i
].r
) {
--cnt
[a
[r
]];--sum
[bl
[a
[r
]]];
if(!cnt
[a
[r
]]) --num
[bl
[a
[r
]]];
--r
;
}
int &res1
=ans1
[qs
[i
].id
]=0,&res2
=ans2
[qs
[i
].id
]=0;int a
=qs
[i
].a
,b
=qs
[i
].b
;
if(bl
[a
]^bl
[b
]) {
for(register int i
=a
;i
<=ri
[bl
[a
]];++i
) {res1
+=cnt
[i
];if(cnt
[i
]) ++res2
;}
for(register int i
=bl
[a
]+1;i
<=bl
[b
]-1;++i
) {res1
+=sum
[i
];res2
+=num
[i
];}
for(register int i
=le
[bl
[b
]];i
<=b
;++i
) {res1
+=cnt
[i
];if(cnt
[i
]) ++res2
;}
}
else for(register int i
=a
;i
<=b
;++i
) {res1
+=cnt
[i
];if(cnt
[i
]) ++res2
;}
}
for(register int i
=0;i
<m
;++i
) printf("%d %d\n",ans1
[i
],ans2
[i
]);
return 0;
}
