Array
Time Limit: 15000/8000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 965 Accepted Submission(s): 312
Problem Description
Given an integer array a[1…n].
Count how many subsegment [L,R] satisfying R−L+1≥1 and there is a kind of integer whose number of occurrences is strictly greater than the sum of others in a[L…R].
Input
The first line contains an integer T(T≤15). Then T test cases follow.
For each test case, input two lines.
For the first line, there is only one integer n (1≤n≤106).
The second line contains n integers describing the array a[1…n], while the restriction 0≤ai≤106 is guaranteed.
∑n<=6∗106
Output
For each test case, output a integer per line, denoting the answer of the problem.
Sample Input
1 10 3303 70463 3303 3303 3303 70463 3303 3303 70463 70463
Sample Output
47
code1:
#define lowbit(x) (x & (-x)) int n, mx; const int ad = 1e6 + 5; ll s1[maxn << 2], s2[maxn << 2], s3[maxn << 2], a[maxn]; map<ll, bool> mp; void add(int pos, ll val, int P) { // int tp = pos; // while(pos <= P){ // s1[pos] += val; // s2[pos] += val * tp; // s3[pos] += val * tp * tp; // pos += lowbit(pos); // } for (int i = pos; i <= P; i += lowbit(i)) { s1[i] += val; s2[i] += val * pos; s3[i] += val * pos * pos; } return; } ll getSum(int pos) { ll ret = 0; // int tp = pos; // while(pos){ // ret += s1[pos] * (tp + 2) * (tp + 1) - s2[pos] * (2 * tp + 3) + s3[pos]; // pos -= lowbit(pos); // } // return (ret >> 1); for (int i = pos; i; i -= lowbit(i)) { ret += s1[i] * (pos + 2) * (pos + 1) - s2[i] * (2 * pos + 3) + s3[i]; } return (ret >> 1); } vector<int> pos[maxn]; int main() { // int _ = read; // while (_--) { n = read; int t = read; ll res = 0; for (int i = 1; i <= n; i++) { a[i] = read; pos[a[i]].push_back(i); } mp.clear(); for (int i = 1; i <= n; i++) { if (mp[a[i]]) continue; pos[a[i]].push_back(n + 1); int prePos = 0; int siz = pos[a[i]].size(); for (int j = 0; j < siz; j++) { int y = 2 * j - prePos + ad; int x = 2 * j - (pos[a[i]][j] - 1) + ad; res += getSum(y - 1); if (x >= 3) res -= getSum(x - 2); add(x, 1, 2 * maxn); add(y + 1, -1, 2 * maxn); prePos = pos[a[i]][j]; } prePos = 0; for (int j = 0; j < siz; ++j) { int y = 2 * j - prePos + ad; int x = 2 * j - (pos[a[i]][j] - 1) + ad; add(x, -1, 2 * maxn); add(y + 1, 1, 2 * maxn); prePos = pos[a[i]][j]; } mp[a[i]] = true; pos[a[i]].clear(); } printf("%lld\n", res); // } return 0; }
code2:
typedef int itn; #define lowbit(x) (x&(-x)) int n,mx; ll s1[maxn << 2],s2[maxn << 2],s3[maxn << 2],a[maxn]; void add(int pos,ll val,int lim){ for(int i=pos;i<=lim;i+= lowbit(i)){ s1[i] += val; s2[i] += val * pos; s3[i] += val * pos * pos; } return ; } ll getSum(int pos){ ll ret = 0; for(int i=pos;i;i -= lowbit(i)){ ret += s1[i] * (pos + 2) * (pos + 1) - s2[i] * (2 * pos + 3) + s3[i]; } return ret >> 1; } vector<int> pos[maxn]; int main() { int _ = read; while(_ --){ n = read; ll ans = 0; unordered_set<int> st; for(int i=1;i<=n;i++){ a[i] = read; st.insert(a[i]); pos[a[i]].push_back(i); } for(auto at: st){ int num = at; pos[num].push_back(n + 1); int siz = pos[num].size(); int prePos = 0; for(int j=0;j<siz;j++){ int y = 2 * j - prePos + maxn; int x = 2 * j - (pos[num][j] - 1) + maxn; ans += getSum(y - 1); if(x >= 3) ans -= getSum(x-2); add(x,1,2 * maxn); add(y + 1,-1,2 * maxn); prePos = pos[num][j]; } prePos = 0; for(int j=0;j<siz;j++){ int y = 2 * j - prePos + maxn; int x = 2 * j - (pos[num][j] - 1) + maxn; add(x,-1,2 * maxn); add(y + 1,1,2 * maxn); prePos = pos[num][j]; } pos[num].clear(); } st.clear(); printf("%lld\n",ans); } return 0; }
