fork(3) download
copy 
  1. #include<bits/stdc++.h>
  2. #include<algorithm>
  3. using namespace std;
  4. #define mp make_pair
  5. long long int arr[200005],query[1000005],memo[200005];
  6. class node
  7. {
  8. 	public:vector< pair<long long int,pair<long long int,long long int> > >link;
  9. };
  10.  
  11. #define vppi pair<long long int,pair<long long int,long long int> >
  12. node dp[600];
  13.  
  14. inline long long int readInt (void) 
  15. {
  16.  
  17.  
  18. 	bool minus = false;
  19. 	long long int result = 0;
  20. 	char ch;
  21. 	ch = getchar();
  22. 	while (true) {
  23. 		if (ch == '-') break;
  24. 		if (ch >= '0' && ch <= '9') break;
  25. 		ch = getchar();
  26. 	}
  27. 	if (ch == '-') minus = true; else result = ch-'0';
  28. 	while (true) {
  29. 		ch = getchar();
  30. 		if (ch < '0' || ch > '9') break;
  31. 		result = result*10 + (ch - '0');
  32. 	}
  33. 	if (minus)
  34. 		return -result;
  35. 	else
  36. 		return result;
  37.  
  38.  
  39.  
  40. }
  41.  
  42. inline void add(long long int i,long long int *answer)
  43. {
  44.     query[arr[i]]++;
  45.     *(answer)=(*answer)+( arr[i]*( (2*query[arr[i]])-1 ) );
  46.  
  47. }
  48.  
  49. inline void remove(long long int i,long long int *answer)
  50. {
  51.     //if(query[arr[i]]>0)
  52.  
  53.     query[arr[i]]--;
  54.  
  55. 	(*answer)=(*answer)-( ( (2*query[arr[i]])+1)*arr[i]  );
  56.  
  57.  
  58. }
  59.  
  60. inline bool compare3( vppi a,vppi b)
  61. {
  62. 	return a.second.second<b.second.second;
  63. }
  64.  
  65. int main()
  66. {
  67. 	long long int t,n,q,i,j,k,sq,a,b,m;
  68. 	n=readInt();
  69. 	m=readInt();
  70. 	for(i=0;i<n;i++)  arr[i]= readInt();
  71. 	sq=ceil( (double)sqrt(n) );
  72. 	//scanint(m);
  73. 	t=m;
  74. 	j=0;
  75. 	while(t--)
  76. 	{ 
  77.  
  78. 	   	a=readInt();
  79. 	   	b=readInt();
  80. 		i=(a-1)/sq;
  81. 	    dp[i].link.push_back(mp(j,mp(a-1,b-1)));
  82. 		j++;
  83.  
  84. 	}
  85.  
  86. 	for(i=0;i<sq;i++)
  87. 	{
  88. 		j=dp[i].link.size();
  89. 		if(j!=0) sort(dp[i].link.begin(),dp[i].link.end(),compare3);
  90. 	}
  91.  
  92. 	memset(query,0,sizeof(query));
  93.  
  94. 	long long int ans=0;
  95.  
  96.  
  97. 	long long int currentL=0,currentR=0,L,R;
  98. 	for(i=0;i<=sq;i++)
  99. 	{
  100. 		j=dp[i].link.size();
  101. 		for(k=0;k<j;k++)
  102. 	    {
  103.  
  104. 	    	L=dp[i].link[k].second.first;
  105. 	    	R=dp[i].link[k].second.second;
  106. 	        while( currentL <L) 
  107. 		    {
  108. 		        remove(currentL,&ans);
  109.                 currentL++;
  110.             }
  111.  
  112. 	        while( currentL >L)
  113.             {
  114.                 add(currentL-1,&ans);
  115.                 currentL--;
  116.             }
  117.             while( currentR <=R)
  118.             {
  119.                add(currentR,&ans);
  120.                currentR++;
  121.             }
  122.             while( currentR >R+1)
  123.             {
  124.                 remove(currentR-1,&ans);
  125.                 currentR--;	
  126. 		    }
  127.  
  128. 		    memo[dp[i].link[k].first]=ans;
  129.  
  130. 	    }
  131.  
  132. 	}
  133.  
  134. 	for(i=0;i<m;i++) 
  135. 	{
  136. 		printf("%I64d\n",memo[i]);
  137. 	}
  138. }
Success #stdin #stdout 0.01s 14368KB
comments (?)
stdin
copy 
8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7
stdout
copy 
                                                              20
                                                              20
                                                              20
https://ideone.com/mc0fNT
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!