TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3278
  • 問題
  • P3278【分块·莫队】我一点也不想给这道题起名字。
    制限 : 時間制限 : 15000 MS   メモリ制限 : 524288 KB
    問題説明

    给一个长度为n的序列a[1],...,a[n]和n个贡献参数w[1],...,w[n]。
    每次提问[l,r],如果权值为x的数出现了k次,则对答案贡献x*w[k],没出现过的数对答案不做贡献,求答案。

    入力形式

    第一行两个数n,m,表示序列长度和提问数目。
    第二行n个数表示序列。
    第三行n个数表示贡献参数。
    接下来m行每行两个数l,r表示一次提问。

    出力形式

    对每次提问输出一行一个数,表示答案。

    サンプル入力 1

    5 3
    1 2 3 1 3 
    9 8 7 6 5 
    1 2
    2 5
    1 5

    サンプル出力 1

    27
    51
    50

    サンプル入力 2

    1 1
    7354389 
    966201 
    1 1

    サンプル出力 2

    7105818006189

    ヒント

    1<=n,m<=100000
    1<=序列中每个数<=10^9
    1<=贡献参数<=10^9
    答案显然不会超过long long范围。


    ソース  “糖果公园”序列版,感谢nodgd抄袭+简化