2015
04-13

# Glorious Array

You are given a array with N nodes. The array nodes are numbered from 1 to N ( represented by a_i ). In the start, the color
of any node in the array is white or black. We define that the "distance" between a and b is min{a_i| a<=i<=b} if a-th and bth
nodes have diffrerent color, or infinite if they have the same color.
We will ask you to perfrom some instructions of the following form:
0 i : change the color of the i-th node (from white to black, or from black to white);
or
1 : ask for the kinds of diffrent pair of nodes’ distance is less than K

The first line contains a positive integer: the number of test cases, at most 100.
After that per test case:
One line with three integers N, m and K (1 ≤ N, m ≤ 1 00000, K ≤ 1000000): the length of the array, the number of
instructions and K which used in operation 1 .
Then comes a line with N intergers a_i (|a_i|<10000000).
A line with N intergers c_i (c_i = 0(white) or 1(black)), which reprsent the color of N nodes.
Next m lines, each will be a instruction described above.

The first line contains a positive integer: the number of test cases, at most 100.
After that per test case:
One line with three integers N, m and K (1 ≤ N, m ≤ 1 00000, K ≤ 1000000): the length of the array, the number of
instructions and K which used in operation 1 .
Then comes a line with N intergers a_i (|a_i|<10000000).
A line with N intergers c_i (c_i = 0(white) or 1(black)), which reprsent the color of N nodes.
Next m lines, each will be a instruction described above.

1
5 3 2
2 3 1 4 2
0 1 0 1 1
1
0 2
1

5
6

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
#define MAXN 100005

int n, m, k;

int num[MAXN], col[MAXN];
int pos[MAXN], sum[MAXN], pre[MAXN];
int pp, ss, tt;

int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d %d %d", &n, &m, &k);
pp = ss = tt = 0;
pos[pp++] = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &num[i]);
if (num[i] < k)
pos[pp++] = i;
}
pos[pp++] = n + 1;
memset(sum, 0, sizeof (sum));
for (int i = 1; i <= n; i++)
{
scanf("%d", &col[i]);
if (num[i] < k)
ss++;
else
sum[ss] += col[i];
sum[pp] += col[i];
}
long long ori = 0;
pre[tt++] = 0;
for (int i = 1; i <= n; i++)
{
if (num[i] < k)
pre[i] = tt++;
else
pre[i] = pre[i - 1];
}
ori = (long long) sum[pp] * (n - sum[pp]);
for (int i = 0; i <= ss; i++)
ori -= (long long) sum[i] * (pos[i + 1] - pos[i] - 1 - sum[i]);

while (m--)
{
int op, x;
scanf("%d", &op);
if (op == 0)
{
scanf("%d", &x);
int pr = pre[x];
ori -= (long long) sum[pp] * (n - sum[pp]);
if (num[x] >= k)
ori += (long long) sum[pr] * (pos[pr + 1] - pos[pr] - 1 - sum[pr]);

if (col[x] == 0)
{
if (num[x] >= k)
sum[pr]++;
sum[pp]++;
}
else
{
if (num[x] >= k)
sum[pr]--;
sum[pp]--;
}

col[x] ^= 1;

ori += (long long) sum[pp] * (n - sum[pp]);
if (num[x] >= k)
ori -= (long long) sum[pr] * (pos[pr + 1] - pos[pr] - 1 - sum[pr]);
}
else
printf("%I64d\n", ori);
}
}
}

1. 题本身没错，但是HDOJ放题目的时候，前面有个题目解释了什么是XXX定律。
这里直接放了这个题目，肯定没几个人明白是干啥

2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.