In this HackerEarth Something Genuine problem Jeffrey is the creator of the Fenêtres operating system, the most popular operating system in the world. Sales are dropping recently, and an initial inquiry into the issue turned up that some people were using pirated versions of Fenêtres. Developers of his company promised to crack down on those users. They implemented a feature — the pirated copy of the operating system would change to a black desktop background and display "This copy of Fenêtres is not genuine." But it's not empty words Jeffrey was after. There was something else he desired all along. He wants the raw data!
Responsibility through the company for this matter kept getting pushed down, until the task came to you, a new hire of the company that owns Fenêtres. You knew that getting all the data for Jeffrey in a reasonable amount of time was out the the question, was out of your reach. Even so, you want something genuine that you can show him!
Therefore, you conducted a survey of N copies of Fenêtres, recording their license numbers in an array. The user count of an array is the number of distinct integers which are present in the array. The value of an array is the square of the user count. You have a trick that will get you N * (N + 1) / 2 sets of data just from your initial array. Instead of getting just one piece of information from your array, you will take all the subarrays of your first array (including the subarray that corresponds to the whole array) and treat them as separate pieces of data! Specifically, the information Jeffrey requires is the sum of the values of each array in your dataset. If you impress Jeffrey now, you'll quickly ascend in the company. Calculating the result by hand is a bit too tedious, so you are going to write a program that does it instead.
HackerEarth Something Genuine problem solution.
#include <bits/stdc++.h>
using namespace std;
const int MOD=1000000007;
int N;
int A[200001];
struct node
{
int sum0, sum1, sum2, lazy;
} seg[524288];
void init(int idx, int begin, int end)
{
if(begin==end)
seg[idx].sum0=1, seg[idx].sum1=seg[idx].sum2=0;
else
{
int mid=(begin+end)/2;
init(idx*2, begin, mid);
init(idx*2+1, mid+1, end);
seg[idx].sum0=seg[idx*2].sum0+seg[idx*2+1].sum0;
}
}
void modify(int idx, int v)
{
seg[idx].sum2=(seg[idx].sum2+2LL*seg[idx].sum1*v+1LL*seg[idx].sum0*v*v)%MOD;
seg[idx].sum1=(seg[idx].sum1+1LL*seg[idx].sum0*v)%MOD;
seg[idx].lazy+=v;
}
void down(int idx)
{
if(seg[idx].lazy)
{
modify(idx*2, seg[idx].lazy);
modify(idx*2+1, seg[idx].lazy);
seg[idx].lazy=0;
}
}
void update(int idx, int begin, int end, int l, int r)
{
if(r<begin || end<l)
return;
if(l<=begin && end<=r)
modify(idx, 1);
else
{
down(idx);
int mid=(begin+end)/2;
update(idx*2, begin, mid, l, r);
update(idx*2+1, mid+1, end, l, r);
seg[idx].sum1=(seg[idx*2].sum1+seg[idx*2+1].sum1)%MOD;
seg[idx].sum2=(seg[idx*2].sum2+seg[idx*2+1].sum2)%MOD;
}
}
int query(int idx, int begin, int end, int l, int r)
{
if(r<begin || end<l)
return 0;
if(l<=begin && end<=r)
return seg[idx].sum2;
down(idx);
int mid=(begin+end)/2;
return (query(idx*2, begin, mid, l, r)+
query(idx*2+1, mid+1, end, l, r))%MOD;
}
int main()
{
scanf("%d", &N);
init(1, 1, N);
int a, ans=0;
for(int i=1; i<=N; i++)
{
scanf("%d", &a);
update(1, 1, N, A[a]+1, i);
ans=(ans+query(1, 1, N, 1, i))%MOD;
A[a]=i;
}
printf("%d\n", ans);
return 0;
}
Second solution
#include <bits/stdc++.h>
using namespace std;
#define jjs(i, s, x) for (int i = (s); i < int(x); i++)
#define jjl(i, x) jjs(i, 0, x)
#define ji(x) jjl(i, x)
#define jj(x) jjl(j, x)
#define jk(x) jjl(k, x)
#define jij(a, b) ji(a) jj(b)
#define ever ;;
#define foreach(x, C) for (auto& x : (C))
#define INF ((int) 1e9+10)
#define LINF ((ll) 1e16)
#define pb push_back
#define mp make_pair
#define nrint(x) int x; rint(x);
#define nrlong(x) long long x; rint(x);
#define rfloat(x) scanf("%lf", &(x))
#ifndef ONLINE_JUDGE
const bool DEBUG = true;
#define Db(x...) ({ if (DEBUG) { cout << "Debug["; DB, #x, ":", x, "]\n"; } })
template<class T> void Dbrng(T lo, T hi, string note = "", int w = 0) {
if (DEBUG) {
cout << "Debug[ ";
if (!note.empty()) cout << setw(3) << note << " : ";
for (; lo != hi; ++lo) cout << setw(w) << *lo << " ";
cout << "]" << endl;
}
}
struct Debugger { template<class T> Debugger& operator ,
(const T & v) { cout << " " << v << flush; return *this; } } DB;
#else
const bool DEBUG = false;
#define Db(x...)
#endif
#define rint readInteger
template<typename T>
bool readInteger(T& x)
{
char c,r=0,n=0;
x=0;
for (ever)
{
c=getchar();
if ((c<0) && (!r))
return(0);
else if ((c=='-') && (!r))
n=1;
else if ((c>='0') && (c<='9'))
x=x*10+c-'0',r=1;
else if (r)
break;
}
if (n)
x=-x;
return(1);
}
typedef pair<int, int> pi;
typedef long long ll;
typedef vector<int> VI;
typedef vector<pi> VPI;
typedef vector<VI> VVI;
const int MX = (int) 2e5;
int N;
int last[MX];
const int TMX = MX * 4;
#define _L (idx*2+1)
#define _R (idx*2+2)
#define _M ((l+r)/2)
ll d0[TMX], d1[TMX], laz[TMX], sz[TMX];
ll v1(ll x)
{
return d1[x] + laz[x] * 2 * sz[x];
}
ll v0(ll x)
{
return d0[x] + (d1[x] + (laz[x] + 1) * sz[x]) * laz[x];
}
void prop(int idx, int l, int r)
{
if (l != r)
{
laz[_L] += laz[idx];
laz[_R] += laz[idx];
laz[idx] = 0;
d1[idx] = v1(_L) + v1(_R);
d0[idx] = v0(_L) + v0(_R);
}
}
void build(int idx, int l, int r)
{
if (l != r)
{
build(_L, l, _M);
build(_R, _M+1, r);
sz[idx] = sz[_L] + sz[_R];
prop(idx, l, r);
}
else
{
sz[idx] = 1;
d1[idx] = -1;
}
}
void upd(int idx, int l, int r, int a, int b)
{
if (a <= l && b >= r)
++laz[idx];
else if (a > r || b < l)
return;
else
{
upd(_L, l, _M, a, b);
upd(_R, _M+1, r, a, b);
}
prop(idx, l, r);
}
int main()
{
rint(N);
assert(1 <= N && N <= MX);
ji(N) last[i] = -1;
build(0, 0, N-1);
ll tot = 0;
ji(N)
{
nrint(x); --x;
upd(0, 0, N-1, last[x]+1, i);
last[x] = i;
tot += v0(0);
tot %= (int) (1e9+7);
}
printf("%lld\n", tot);
}
0 Comments