首页 > ACM题库 > HDU-杭电 > HDU 3854-Glorious Array[解题报告]HOJ
2015
04-13

HDU 3854-Glorious Array[解题报告]HOJ

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.