[线性dp]Burenka and Traditions Codeforces1719D1&&D2

This is the hard version of this problem. The difference between easy and hard versions is only the constraints on aiai and on nn. You can make hacks only if both versions of the problem are solved.

Burenka is the crown princess of Buryatia, and soon she will become the nn-th queen of the country. There is an ancient tradition in Buryatia — before the coronation, the ruler must show their strength to the inhabitants. To determine the strength of the nn-th ruler, the inhabitants of the country give them an array of aa of exactly nn numbers, after which the ruler must turn all the elements of the array into zeros in the shortest time. The ruler can do the following two-step operation any number of times:

• select two indices ll and rr, so that 1≤l≤r≤n1≤l≤r≤n and a non-negative integer xx, then
• for all l≤i≤rl≤i≤r assign ai:=ai⊕xai:=ai⊕x, where ⊕⊕ denotes the bitwise XOR operation. It takes ⌈r−l+12⌉⌈r−l+12⌉ seconds to do this operation, where ⌈y⌉⌈y⌉ denotes yy rounded up to the nearest integer.

Help Burenka calculate how much time she will need.

Input

The first line contains a single integer tt (1≤t≤500)(1≤t≤500)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer nn (1≤n≤105)(1≤n≤105) - the size of the array

The second line of each test case contains nn integers a1,a2,⋯,ana1,a2,⋯,an (0≤ai<230)(0≤ai<230) — elements of the array.

It is guaranteed that the sum of nn in all tests does not exceed 105105.

Output

For each test case, output a single number  — the minimum time that Burenka will need.

Example

input

7

4

5 5 5 5

3

1 3 2

2

0 0

3

2 5 7

6

1 2 3 3 2 1

10

27 27 34 32 2 31 23 56 52 4

5

1822 1799 57 23 55

output

2

2

0

2

4

7

4

题意： 对区间[l, r]内的数字可以全部异或上一个数字x，代价为区间长度除2上取整，x值可以任取，求让整个数组全0的最小代价。

分析： 区间长度为1和2时代价都是1，区间长度为3和4时代价都是2，可以发现大区间能够拆分为若干小区间且代价不变，而多个小区间肯定比一个大区间更优的，毕竟有更多的x可以选择，所以最终实际上就是选择长度为2或者长度为1的区间进行操作，从前往后看，每次操作具体异或值x应该是a[i]，这样才能使其为0，虽然值是确定的，但是长度却是可以选择的，要么只取其本身，要么再往后延长一个长度，而后者就有可能让整体代价减少，因为当出现一段区间[l, r]的异或和为0时，对[l, r]上每个数取长度为2的操作，这样到a[r]的时候不用操作都是0了，这就节省了一次操作。

设dp[i]表示将前i个元素全部置0的最小代价，状态转移就是选择一个最大的j，使得[j, i]的区间异或和为0，令dp[i] = min(dp[i-1]+a[i]!=0，dp[j-1]+j-i)，选择最大的j其实是个优化，理论上是要对于所有右端点为i的异或和为0的区间进行统计，但是由于左端点小于最大的j是不优的，所以直接选最大的j就行。而对于某个i其最大的j可以用map来存一下，这样总的复杂度就是O(nlogn)。

具体代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
using namespace std;
int dp[100005];//dp[i]记录前i个数置为0所需的最小代价
int a[100005], sum[100005];
int last[100005];
map<int, int> mp;
signed main()
{
int T;
cin >> T;
while(T--){
int n;
scanf("%d", &n);
mp.clear();
mp[0] = 0;
for(int i = 1; i <= n; i++) last[i] = -1;
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
sum[i] = sum[i-1]^a[i];
if(mp.count(sum[i]))
last[i] = mp[sum[i]];
mp[sum[i]] = i;
}
dp[1] = (a[1]!=0);
for(int i = 2; i <= n; i++){
dp[i] = dp[i-1]+(a[i]!=0);
if(last[i] != -1)
dp[i] = min(dp[i], dp[last[i]]+(i-last[i]-1));
}
printf("%dn", dp[n]);
}
return 0;
}
 

最后

以上就是傻傻康乃馨为你收集整理的[线性dp]Burenka and Traditions Codeforces1719D1&&D2的全部内容，希望文章能够帮你解决[线性dp]Burenka and Traditions Codeforces1719D1&&D2所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。