F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 3289 >> 莫队+离散化树状数组WA
ForwardStar @ 2019-10-28 09:38:55
[ Quote ] [ Edit ] [ Delete ] 1#
#include<cstdio>
#include<algorithm>
#include<cmath>
#pragma GCC optimize(2)
using namespace std;
struct newdata
{
int l,r,label;
};
struct newdata1
{
int v,label;
};
int n,q,cnt;
newdata1 a[50001];
int b[50001];
int belong[50001];
int tree[50001];
int ans[50001];
newdata query[50001];
bool cmp(newdata i,newdata j)
{
return ((belong[i.l] ^ belong[j.l]) ? (belong[i.l] < belong[j.l]) : (belong[i.l] & 1) ? (i.r < j.r) : (i.r > j.r));
}
bool cmp1(newdata1 i,newdata1 j)
{
return i.v < j.v;
}
inline int lowbit(int x)
{
return x & (-x);
}
void add(int now,int x)
{
int i = now;
while (i <= n)
{
tree[i] += x;
i += lowbit(i);
}
}
int count(int now)
{
int i = now;
int tot = 0;
while (i > 0)
{
tot += tree[i];
i -= lowbit(i);
}
return tot;
}
int main()
{
scanf("%d",&n);
for (int i = 1;i <= n;i ++)
{
scanf("%d",&a[i].v);
a[i].label = i;
}
sort(a + 1,a + n + 1,cmp1);
int tt = 1;
b[a[1].label] = 1;
for (int i = 2;i <= n;i ++)
if (b[i] != b[i - 1])
{
tt ++;
b[a[i].label] = tt;
}
else b[a[i].label] = tt;
int size = int(sqrt(n));
int num = ceil(double(n) / size);
for (int i = 1;i <= num;i ++)
for (int j = (i - 1) * size + 1;j <= min(n,i * size);j ++)
belong[j] = i;
scanf("%d",&q);
for (int i = 1;i <= q;i ++)
{
scanf("%d%d",&query[i].l,&query[i].r);
query[i].label = i;
}
sort(query + 1,query + q + 1,cmp);
int l = 1;
int r = 0;
int now = 0;
for (int i = 1;i <= q;i ++)
{
while (r < query[i].r)
{
r ++;
now += cnt - count(b[r]);
cnt ++;
add(b[r],1);
}
while (r > query[i].r)
{
cnt --;
add(b[r],-1);
now -= cnt - count(b[r]);
r --;
}
while (l < query[i].l)
{
cnt --;
add(b[l],-1);
now -= count(b[l] - 1);
l ++;
}
while (l > query[i].l)
{
l --;
now += count(b[l] - 1);
cnt ++;
add(b[l],1);
}
ans[query[i].label] = now;
}
for (int i = 1;i <= q;i ++)
printf("%d\n",ans[i]);
return 0;
}
ForwardStar @ 2019-10-28 09:45:49
[ Quote ] [ Edit ] [ Delete ] 2#
A掉了!犯了一个小失误。。
[Top] [Previous Page] [Next Page]

HOME Back