?

• [1457] Sona

• 時(shí)間限制: 5000 ms　內(nèi)存限制: 65535 K
• 問(wèn)題描述
• Sona,?Maven of the Strings. Of cause, she can play the zither.

  ?

  Sona?can't speak but she can make fancy music. Her music can attack, heal, encourage and enchant.

  ?

  There're an ancient?score(樂(lè)譜). But because it's too long,?Sona?can't play it in a short moment. So?Sona?decide to just play a part of it and revise it.

  ?

  A score is composed of notes. There?are?109?kinds of notes and a score has105?notes at most.

  ?

  To diversify?Sona's own score, she have to select several parts of it. The energy of each part is calculated like that:

  ?

  Count the number of times that each notes appear. Sum each of the number of times' cube together. And the sum is the energy.

  ?

  You should help?Sona?to calculate out the energy of each part.

• 輸入
• This problem contains several cases. And this problem provides 2 seconds to run.
  The first line of each case is an integer N (1 ≤ N ≤ 10^5), indicates the number of notes.
  Then N numbers followed. Each number is a kind of note. (1 ≤ NOTE ≤ 10^9)
  Next line is an integer Q (1 ≤ Q ≤ 10^5), indicates the number of parts.
  Next Q parts followed. Each part contains 2 integers Li and Ri, indicates the left side of the part and the right side of the part.
• 輸出
• For each part, you should output the energy of that part.
• 樣例輸入

• 8
  1 1 3 1 3 1 3 3
  4
  1 8
  3 8
  5 6
  5 5
  

• 樣例輸出

• 128
  72
  2
  1

?

?

題目鏈接：NBUT 1457

莫隊(duì)算法就是能用n*sqrt（n）的時(shí)間來(lái)解決無(wú)修改區(qū)間查詢的一種辦法……，主要處理就是把詢問(wèn)暫時(shí)不按照讀入順序而按照所在塊和右端點(diǎn)值為關(guān)鍵字進(jìn)行排序，然后對(duì)這樣的一個(gè)暫時(shí)非正常的詢問(wèn)順序進(jìn)行計(jì)算回答，然后可以再次按照輸入順序排序或者用數(shù)組記錄答案后輸出。

可以參考這篇博客：莫隊(duì)算法經(jīng)典例題

這題寫(xiě)出立方公式就很容易發(fā)現(xiàn)a^3和（a+1）^3以及（a-1）^3的區(qū)別，然后就可以很方便地進(jìn)行O（1）轉(zhuǎn)化，網(wǎng)上一些題解代碼都是暴力減掉當(dāng)前的再加回更新的，即減掉a*a*a再加上(a+1)*(a+1)*(a+1)，感覺(jué)這樣寫(xiě)不太好……，反正如果能快速得到[L-1,R]或[L,R+1]這樣的區(qū)間信息的話莫隊(duì)算法值得一試。這題用了輸入輸出外掛搞到2100+MS，一些人直接用立方加減的3300+MS

代碼：

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<bitset>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef __int64 LL;
const double PI=acos(-1.0);
const int N=100010;struct info
{int l;int r;LL energy;int id;
};
info node[N];
LL arr[N];
int unit,b[N];
LL cnt[N];
LL ans[N];
inline bool cmp(const info &a,const info &b)
{if(a.l/unit!=b.l/unit)return a.l/unit<b.l/unit;return a.r<b.r;
}void init()
{CLR(arr,0);CLR(cnt,0);
}
inline void update(int pos,int n,LL &temp)
{LL &val=arr[pos];if(n==1)temp=temp+3*cnt[val]*cnt[val]+3*cnt[val]+1;elsetemp=temp-3*cnt[val]*cnt[val]+3*cnt[val]-1;cnt[val]+=n;	
}
int Scan()
{int res=0,ch,flag=0;if((ch=getchar())=='-')flag=1;else if(ch>='0'&&ch<='9')res=ch-'0';while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-'0';return flag?-res:res;
}
void Out(LL a)
{if(a>9)Out(a/10LL);putchar(a%10LL+'0');
}
int main(void)
{int n,i,j,k,L,R;while (~scanf("%d",&n)){for (i=1; i<=n; ++i){arr[i]=Scan();b[i]=arr[i];}sort(b+1,b+1+n);int m=unique(b+1,b+1+n)-b-1;for (i=1; i<=n; ++i)arr[i]=lower_bound(b+1,b+1+m,arr[i])-b;unit=(int)sqrt(1.0*n);scanf("%d",&k);for (i=0; i<k; ++i){node[i].l=Scan();node[i].r=Scan();node[i].id=i;}sort(node,node+k,cmp);L=node[0].l;R=node[0].l-1;LL temp=0;for (i=0; i<k; ++i){while (L>node[i].l)update(--L,1,temp);while (R<node[i].r)update(++R,1,temp);while (L<node[i].l)update(L++,-1,temp);while (R>node[i].r)update(R--,-1,temp);ans[node[i].id]=temp;}for (i=0; i<k; ++i){Out(ans[i]);putchar('\n');}init();}return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/Blackops/p/5766255.html

總結(jié)

以上是生活随笔為你收集整理的NBUT 1457 Sona（莫队算法+离散化）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。