Little Mishka is a great traveller and she visited many countries. After thinking about where to travel this time, she chose XXX — beautiful, but little-known northern country.
Here are some interesting facts about XXX:
- XXX consists of n cities, k of whose (just imagine!) are capital cities.
- All of cities in the country are beautiful, but each is beautiful in its own way. Beauty value of i-th city equals toci.
- All the cities are consecutively connected by the roads, including 1-st and n-th city, forming a cyclic route1 — 2 — ... — n — 1. Formally, for every 1 ≤ i < n there is a road between i-th and i + 1-th city, and another one between 1-st and n-th city.
- Each capital city is connected with each other city directly by the roads. Formally, if city x is a capital city, then for every 1 ≤ i ≤ n, i ≠ x, there is a road between cities x and i.
- There is at most one road between any two cities.
- Price of passing a road directly depends on beauty values of cities it connects. Thus if there is a road between cities i and j, price of passing it equals ci·cj.
Mishka started to gather her things for a trip, but didn't still decide which route to follow and thus she asked you to help her determine summary price of passing each of the roads in XXX. Formally, for every pair of cities a and b(a < b), such that there is a road between a and b you are to find sum of products ca·cb. Will you help her?
The first line of the input contains two integers n and k (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n) — the number of cities in XXX and the number of capital cities among them.
The second line of the input contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 10 000) — beauty values of the cities.
The third line of the input contains k distinct integers id1, id2, ..., idk (1 ≤ idi ≤ n) — indices of capital cities. Indices are given in ascending order.
Print the only integer — summary price of passing each of the roads in XXX.
4 1
2 3 1 2
3
17
5 2
3 5 2 2 4
1 4
71
This image describes first sample case:
It is easy to see that summary price is equal to 17.
This image describes second sample case:
It is easy to see that summary price is equal to 71.
题意：给你n个点，n个点按标号一次首位相接，其中有m个特殊的点，这m个点跟其他的所有点都相连接，点之间连接的线
的权值为点的权值之积，任意两个点之间至多一条边，最后问你整个图边的权值之和
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MM(a,b) memset(a,b,sizeof(a));
#define inf 0x7f7f7f7f
#define FOR(i,n) for(int i=1;i<=n;i++)
#define CT continue;
#define PF printf
#define SC scanf
const int mod=1000000007;
const int N=1e5+100;
int ncap[N],flag[N];
ll a[N];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
ll all=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
all+=a[i];
}
a[n+1]=a[1];
a[0]=a[n];
for(int i=1;i<=m;i++) scanf("%d",&ncap[i]);
ll ans=0,tmp=0;
for(int i=1;i<=n;i++) ans+=a[i+1]*a[i];
MM(flag,0);
for(int i=1;i<=m;i++)
{
int cur=ncap[i],l=cur-1,r=cur+1;
flag[cur]=1;
if(l==0) l=n;
if(r==n+1) r=1;
ans+=a[cur]*(all-a[cur]-tmp);
if(!flag[l]) ans-=a[cur]*a[l];
if(!flag[r]) ans-=a[cur]*a[r];
tmp+=a[cur];
}
printf("%lld
",ans);
}
return 0;
}
分析：有点锻炼思维，首先ans初始值为n个点围成的一个圈的边权值之和，然后对于每个特殊的点，它所能增加的边权值之和
为 该点权值（ 所有点的权值之和-该点权值-先前遍历过的特殊的点的权值-与其在环上直接相连的两点权值之和）
不过有时候因为先前遍历过的点可能跟与在环上直接相连的点有重合，所以要设置一个flag，避免再被减一
次。