题意：
有n个球。它们排成一排。每个球都有一个颜色（为方便起见，为整数）和一个整数值。第i个球的颜色为ci，第i个球的值为vi。
松鼠Liss选择了一些球，并在不改变球相对顺序的情况下做出了新的顺序。她想最大化此序列的价值。
序列的值定义为每个球的以下值的总和（其中a和b为常数）：
如果该球不在序列的开头，并且该球的颜色与上一个球的颜色相同，请添加（球的值）×a。
否则，加上（球的值）×b。
给出q个查询。每个查询包含两个整数ai和bi。对于每个查询，找到当a = ai和b = bi时她可以做出的序列的最大值。
请注意，新序列可以为空，并且空序列的值定义为零。
输入项
第一行包含两个整数n和q（1≤n≤105; 1≤q≤500）。第二行包含n个整数：v1，v2，...，vn（| vi |≤105）。第三行包含n个整数：c1，c2，...，cn（1≤ci≤n）。
接下来的q行包含查询的常量a和b的值。这些行的第i个包含两个整数ai和bi（| ai |，| bi |≤105）。
在每一行中，整数用单个空格分隔。
输出量
对于每个查询，输出包含整数的行-查询的答案。第i行按输入顺序包含第i个查询的答案。
请不要编写％lld说明符来以С++读取或写入64位整数。最好使用cin，cout流或％I64d说明符。
题解：
卡线段树。
/* *author: zlc *zucc_acm_lab *just do it */ #include<bits/stdc++.h> using namespace std; typedef long long ll; const double pi=acos(-1.0); const double eps=1e-6; const int mod=1e9+7; const ll inf=1e18; const int maxn=1e6+100; inline ll read () {ll x=0;ll f=1;char ch=getchar();while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;} //inline int read () {int x=0;int f=1;char ch=getchar();while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;} ll qpow (ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll n,m; ll a[maxn]; ll c[maxn]; ll dp[maxn]; ll ans; ll tot; int main () { n=read();m=read(); for (int i=1;i<=n;i++) a[i]=read(); for (int i=1;i<=n;i++) c[i]=read(); while (m--) { tot=0; ll u,v; u=read();v=read(); for (int i=1;i<=n;i++) dp[i]=-inf; ans=0; ll t1=0,t2=0; for (int i=1;i<=n;i++) { ans=max(v*a[i],dp[c[i]]+u*a[i]); if (c[i]!=t1) ans=max(ans,dp[t1]+v*a[i]); else ans=max(ans,dp[t2]+v*a[i]); if (ans>dp[t1]) { if (t1!=c[i]) { t2=t1; t1=c[i]; } else { t1=c[i]; } } else if (ans>dp[t2]&&c[i]!=t1) t2=c[i]; dp[c[i]]=max(dp[c[i]],ans); tot=max(tot,ans); } printf("%lld ",tot); } }