程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 3872 Beauty of Array（數學）

ZOJ 3872 Beauty of Array（數學）

編輯：C++入門知識

ZOJ 3872 Beauty of Array（數學）

Beauty of Array

Time Limit: 2 Seconds Memory Limit: 65536 KB

Edward has an array A with N integers. He defines the beauty of an array as the summation of all distinct integers in the array. Now Edward wants to know the summation of the beauty of all contiguous subarray of the array A.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains an integer N (1 <= N <= 100000), which indicates the size of the array. The next line contains N positive integers separated by spaces. Every integer is no larger than 1000000.

Output

For each case, print the answer in one line.

Sample Input

Sample Output

105
21
38

題意：定義一個序列的美麗值為序列中不同數的和，求一個序列的所有子序列的美麗值的和

思路：在代碼中，關鍵是理解我C(x,2)代表取得區間是左開右閉的

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include


#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

#define eps 1e-8
typedef long long ll;

#define fre(i,a,b)  for(i = a; i = a;i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define ssf(n)      scanf("%s", n)
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf          printf
#define bug         pf("Hi\n")

using namespace std;

#define INF 0x3f3f3f3f
#define N 1000005

int ha[N],hato[N];
int a[N],b[N];
vectorg[N];
int n;
int k;

void solve()
{
	int i,j;
	ll ans=0;
	ll temp;
	fre(i,0,k)
	{

		ans+=(long long)(n)*(n+1)/2*hato[i]; //根據德保大神點撥，
		temp=0;                           //例如一個區間有3的位置為(這裡用真實位置，不是從0開始)
										  //    3 ..  5... 8    假設在0位置有一個3
										  //那麼有3的位置  0    3    5     8
										  //因為加了0，所以序列一共n+1個數，假設n+1個數都是3
										  //，現在任取兩個數s,e作為
										  //有效區間為[s+1，e]時,那麼就會加一個3，此時是上面那一步
										  //現在因為兩個3之間並不都是3
										  //所以要去重，假設兩個3之間的數的數目，設為x，那麼應該x++,
										  //因為下面的C(x,2)代表取得區間的有效值是做開右閉的
										  //去掉的個數應該是C(x,2),當然減去的東西應該 再  * 3（這裡的3代表原序列相同的數）
		fre(j,0,g[i].size())
		{
			ll tt=g[i][j]+1-temp;
			ans-=(tt)*(tt-1)/2*hato[i];
			temp=g[i][j]+1;
		}
		ll tt=n+1-temp;
		ans-=(tt)*(tt-1)/2*hato[i];
	}

  pf("%lld\n",ans);
}

int main()
{
   int i,j,t;
   sf(t);
   while(t--)
   {
   	  sf(n);
   	  fre(i,0,n)
   	  {
   	  	sf(a[i]);
   	  	b[i]=a[i];
   	  }

      sort(b,b+n);
      k=unique(b,b+n)-b; //擔心數據太大，哈希預處理

      for(i=0;i