题目描述

样例输入1

5 3
1 2 3 1 3 
9 8 7 6 5 
1 2
2 5
1 5

样例输出1

27
51
50

样例输入1

1 1
7354389 
966201 
1 1

样例输出1

7105818006189

我的 WA35 分代码

#include <algorithm>
#include <iostream>
#include <cmath>
#define int long long
#define debug printf("happy\n")

using namespace std;

const int N = 100005;
int a[N], w[N], belong[N], cnt[N], anses[N], b[N], c[N];
int n, m, s, ans;

struct node
{
	int l, r, id;
	
	bool operator < (const node& x)
{
	if (belong[l] == belong[x.l]) return r < x.r;
	return belong[l] < belong[x.l];
}
} q[N];

inline int read()
{
	int x = 0, y = 1;
	char c = getchar();
	while (c < '0' || c > '9')
	{
		if (c == '-') y = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * y;
}

void change(int x, int opt)
{
	ans -= b[x] * w[cnt[x]];
	cnt[x] += opt;
	ans += b[x] * w[cnt[x]];
}

signed main()
{
	n = read();
	m = read();
	s = sqrt(n);
	
	for (int i = 1; i <= n; i = -~ i)
	{
		a[i] = read();
		b[i] = a[i];
		belong[i] = (i - 1) / s + 1;
	}
	sort(b + 1, b + 1 + n);
	unique(b + 1, b + 1 + n);
	for (int i = 1; i <= n; i = -~ i)
	{
		w[i] = read();
		c[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
	}
	for (int i = 1; i <= m; i = -~ i)
	{
		q[i].l = read();
		q[i].r = read();
		q[i].id = i;
	}
	sort(q + 1, q + 1 + m);
	
	int l = 1, r = 0;
	for (int i = 1; i <= m; i = -~ i)
	{
		while (r < q[i].r) change(c[ ++ r], 1);
		while (r > q[i].r) change(c[r -- ], -1);
		while (l < q[i].l) change(c[l ++ ], -1);
		while (l < q[i].l) change(c[ ++ l], 1);
		
		anses[q[i].id] = ans;
	}
	
	for (int i = 1; i <= m; i = -~ i)
	{
		printf("%lld\n", anses[i]);
	}
	return 0;
}