One day, $ n $ people ( $ n $ is an even number) met on a plaza and
made two round dances, each round dance consists of exactly $ $ people.
Your task is to find the number of ways $ n $ people can make two round
dances if each round dance consists of exactly $ $ people. Each person
should belong to exactly one of these two round dances.
Round dance is a dance circle consisting of $ 1 $ or more people. Two
round dances are indistinguishable (equal) if one can be transformed to
another by choosing the first participant. For example, round dances $
[1, 3, 4, 2] $ , $ [4, 2, 1, 3] $ and $ [2, 1, 3, 4] $ are
indistinguishable.
For example, if $ n=2 $ then the number of ways is $ 1 $ : one round
dance consists of the first person and the second one of the second
person.
For example, if $ n=4 $ then the number of ways is $ 3 $ . Possible
options:
one round dance — $ [1,2] $ , another — $ [3,4] $ ;
one round dance — $ [2,4] $ , another — $ [3,1] $ ;
one round dance — $ [4,1] $ , another — $ [3,2] $ .
Your task is to find the number of ways $ n $ people can make two
round dances if each round dance consists of exactly $ $ people.
输入格式
The input contains one integer $ n $ ( $ 2 n $ ), $ n $ is an even
number.
输出格式
Print one integer — the number of ways to make two round dances. It
is guaranteed that the answer fits in the $ 64 $ -bit integer data
type.
There are $ n $ districts in the town, the $ i $ -th district belongs
to the $ a_i $ -th bandit gang. Initially, no districts are connected to
each other.
You are the mayor of the city and want to build $ n-1 $ two-way roads
to connect all districts (two districts can be connected directly or
through other connected districts).
If two districts belonging to the same gang are connected directly
with a road, this gang will revolt.
You don't want this so your task is to build $ n-1 $ two-way roads in
such a way that all districts are reachable from each other (possibly,
using intermediate districts) and each pair of directly connected
districts belong to different gangs, or determine that it is impossible
to build $ n-1 $ roads to satisfy all the conditions.
You have to answer $ t $ independent test cases.
输入格式
The first line of the input contains one integer $ t $ ( $ 1 t $ ) —
the number of test cases. Then $ t $ test cases follow.
The first line of the test case contains one integer $ n $ ( $ 2 n $
) — the number of districts. The second line of the test case contains $
n $ integers $ a_1, a_2, , a_n $ ( $ 1 a_i ^9 $ ), where $ a_i $ is the
gang the $ i $ -th district belongs to.
It is guaranteed that the sum of $ n $ does not exceed $ 5000 $ ( $ n
$ ).
输出格式
For each test case, print:
NO on the only line if it is impossible to connect all districts
satisfying the conditions from the problem statement.
YES on the first line and $ n-1 $ roads on the next $ n-1 $ lines.
Each road should be presented as a pair of integers $ x_i $ and $ y_i $
( $ 1 x_i, y_i n; x_i y_i $ ), where $ x_i $ and $ y_i $ are two
districts the $ i $ -th road connects.
For each road $ i $ , the condition $ a[x_i] a[y_i] $ should be
satisfied. Also, all districts should be reachable from each other
(possibly, using intermediate districts).
There are $ n $ piranhas with sizes $ a_1, a_2, , a_n $ in the
aquarium. Piranhas are numbered from left to right in order they live in
the aquarium.
Scientists of the Berland State University want to find if there is
dominant piranha in the aquarium. The piranha is called dominant if it
can eat all the other piranhas in the aquarium (except itself, of
course). Other piranhas will do nothing while the dominant piranha will
eat them.
Because the aquarium is pretty narrow and long, the piranha can eat
only one of the adjacent piranhas during one move. Piranha can do as
many moves as it needs (or as it can). More precisely:
The piranha $ i $ can eat the piranha $ i-1 $ if the piranha $ i-1 $
exists and $ a_{i - 1} < a_i $ .
The piranha $ i $ can eat the piranha $ i+1 $ if the piranha $ i+1 $
exists and $ a_{i + 1} < a_i $ .
When the piranha $ i $ eats some piranha, its size increases by one (
$ a_i $ becomes $ a_i + 1 $ ).
Your task is to find any dominant piranha in the aquarium or
determine if there are no such piranhas.
Note that you have to find any (exactly one) dominant piranha, you
don't have to find all of them.
For example, if $ a = [5, 3, 4, 4, 5] $ , then the third piranha can
be dominant. Consider the sequence of its moves:
The piranha eats the second piranha and $ a $ becomes $ [5, , 4, 5]
$ (the underlined piranha is our candidate).
The piranha eats the third piranha and $ a $ becomes $ [5, , 5] $
.
The piranha eats the first piranha and $ a $ becomes $ [, 5] $
.
The piranha eats the second piranha and $ a $ becomes $ [] $ .
You have to answer $ t $ independent test cases.
输入格式
The first line of the input contains one integer $ t $ ( $ 1 t ^4 $ )
— the number of test cases. Then $ t $ test cases follow.
The first line of the test case contains one integer $ n $ ( $ 2 n ^5
$ ) — the number of piranhas in the aquarium. The second line of the
test case contains $ n $ integers $ a_1, a_2, , a_n $ ( $ 1 a_i ^9 $ ),
where $ a_i $ is the size of the $ i $ -th piranha.
It is guaranteed that the sum of $ n $ does not exceed $ 3 ^5 $ ( $ n
^5 $ ).
输出格式
For each test case, print the answer: -1 if there are no dominant
piranhas in the aquarium or index of any dominant piranha otherwise. If
there are several answers, you can print any.
The first test case of the example is described in the problem
statement.
In the second test case of the example, there are no dominant
piranhas in the aquarium.
In the third test case of the example, the fourth piranha can firstly
eat the piranha to the left and the aquarium becomes $ [4, 4, 5, 4] $ ,
then it can eat any other piranha in the aquarium.
You are given a sequence A of N(N <= 100,000) positive integers. There sum will be less than 10 $ ^{18} $ . On this sequence you have to apply M (M <= 100,000) operations:
(A) For given x,y, for each elements between the x-th and the y-th ones (inclusively, counting from 1), modify it to its positive square root (rounded down to the nearest integer).
(B) For given x,y, query the sum of all the elements between the x-th and the y-th ones (inclusively, counting from 1) in the sequence.
## 输入格式
Multiple test cases, please proceed them one by one. Input terminates by EOF.
For each test case:
The first line contains an integer N. The following line contains N integers, representing the sequence A $ _{1} $ ..A $ _{N} $ . The third line contains an integer M. The next M lines contain the operations in the form "i x y".i=0 denotes the modify operation, i=1 denotes the query operation.
## 输出格式
For each test case:
Output the case number (counting from 1) in the first line of output. Then for each query, print an integer as the problem required.
```cpp #include<bits/stdc++.h> #define lson (node<<1)//左儿子 #define rson (node<<1|1)//右儿子 #define ll long long #define int long long //记得开long long using namespace std; const int MAXN = 100005; struct st{ int l,r;//左右端点 ll sum; }tree[MAXN<<2];
int n; //t[i]表示树状数组i结点覆盖的范围和 int a[N], t[N]; //Lower[i]表示左边比第i个位置小的数的个数 //Greater[i]表示左边比第i个位置大的数的个数 int Lower[N], Greater[N];
//返回非负整数x在二进制表示下最低位1及其后面的0构成的数值 intlowbit(int x) { return x & -x; }
//将序列中第x个数加上k。 voidadd(int x, int k) { for(int i = x; i <= n; i += lowbit(i)) t[i] += k; } //查询序列前x个数的和 intask(int x) { int sum = 0; for(int i = x; i; i -= lowbit(i)) sum += t[i]; return sum; }
intmain() {
scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
//从左向右，依次统计每个位置左边比第i个数y小的数的个数、以及大的数的个数 for(int i = 1; i <= n; i++) { int y = a[i]; //第i个数
//在前面已加入树状数组的所有数中统计在区间[1, y - 1]的数字的出现次数 Lower[i] = ask(y - 1);
voidchange(int p, int x, longlong v){ if (t[p].l == t[p].r) { t[p].dat += v; return; } int mid = (t[p].l + t[p].r) / 2; if (x <= mid) change(p*2, x, v); elsechange(p*2+1, x, v); t[p].dat = gcd(t[p*2].dat, t[p*2+1].dat); }
longlongask(int p, int l, int r){ if (l <= t[p].l && r >= t[p].r) returnabs(t[p].dat); int mid = (t[p].l + t[p].r) / 2; longlong val = 0; if (l<=mid) val = gcd(val, ask(p*2, l, r)); if (r>mid) val = gcd(val, ask(p*2+1, l, r)); returnabs(val); }
longlongsum(int x){ longlong y = 0; for (; x; x -= x & -x) y += c[x]; return y; }
voidadd(int x, longlong y){ for (; x <= n; x += x & -x) c[x] += y; }
intmain(){ cin >> n >> m; for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); b[i] = a[i] - a[i-1]; } build(1, 1, n); for (int i = 1; i <= m; i++) { char str[2]; scanf("%s", str); int l, r; scanf("%d%d", &l, &r); if (str[0] == 'Q') { longlong al = a[l] + sum(l); longlong val = l < r ? ask(1, l + 1, r) : 0; printf("%lld\n", gcd(al, val)); } else { longlong delta; scanf("%lld", &delta); change(1, l, delta); if (r < n) change(1, r + 1, -delta); add(l, delta); add(r + 1, -delta); } } }
