City

C++11(clang++ 3.9) 解法, 执行用时: 856ms, 内存消耗: 65176K, 提交时间: 2019-01-07 17:02:45
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(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 gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=101000;
const int inf=1000001;

int n,m,k,x[N],y[N],a[N],b[N],c[N],col[N],row[N],xa,ya,q;

struct linearwise {
 bool fg=0;
 vector<PII> p;
 vector<ll> sa,sc;
 ll z;
 void init() {
  fg=0; z=0;
  p.clear();
  sa.clear(); sc.clear();
 }
 void rebuild() {
  fg=1;
  sort(all(p));
  sa.clear(); sc.clear();
  ll pa=0,pc=0;
  rep(i,0,SZ(p)) {
   pc+=p[i].se;
   pa+=1ll*p[i].fi*p[i].se;
   sa.pb(pa); sc.pb(pc);
  }
 }
 ll query(int x) {
  if (p.empty()) return 0;
  if (!fg) rebuild();
  auto it=lower_bound(all(p),mp(x,-inf*2))-p.begin();
  ll pc=it?sc[it-1]:0,pa=it?sa[it-1]:0;
  return z+pc*x-pa+(sa.back()-pa-(sc.back()-pc)*x);
 }
 void add(ll aa,ll cc) {
  // c |x-a|
  fg=0;
  p.pb(mp(aa,cc));
 }
 void add(ll cc) {
  z+=cc;
 }
};

linearwise allr,allc,segc[N],segr[N];
map<int,linearwise> ssegc[N],ssegr[N];
ll gao(int *x,int *a,int *c,int n,int m) {
 int l=0,r=n-1;
 auto eval=[&](int k) {
  ll s=0;
  rep(i,0,m) s+=(ll)c[i]*abs(x[k]-a[i]);
  return s;
 };
 while (l+3<r) {
  int fl=(l+l+r)/3,fr=(l+r+r)/3;
  ll sl=eval(fl),sr=eval(fr);
  if (sl>sr) l=fl; else r=fr;
 }
 ll ans=1ll<<60;
 //cout << l << ' ' <<r <<endl;
 rep(i,l,r+1) ans=min(ans,eval(i));
 //cout << eval(0) << ' ' <<eval(1) << endl;
 return ans;
}

ll query(int a,int b) {
 int r=upper_bound(x,x+m+2,a)-x-1;
 int c=upper_bound(y,y+n+2,b)-y-1;
 //printf("%d %d %d %d %d %d\n",r,c,x[r],y[c],a,b);
 if (x[r]==a&&y[c]==b) {
  return allr.query(a)+allc.query(b);
 }
 if (x[r]==a) {
  ll ans=allr.query(a)+allc.query(b)+segc[c].query(b);
  if (ssegc[c].count(r)) ans+=ssegc[c][r].query(b);
  return ans;
 }
 if (y[c]==b) {
  ll ans=allr.query(a)+allc.query(b)+segr[r].query(a);
  if (ssegr[r].count(c)) ans+=ssegr[r][c].query(a);
  return ans;  
 }
 assert(0);
 return 0;
}
int main() {
 scanf("%d%d%d",&n,&m,&k);
 y[0]=-inf; y[n+1]=2*inf;
 x[0]=-inf; x[m+1]=2*inf;
 rep(i,1,n+1) scanf("%d",y+i);
 rep(i,1,m+1) scanf("%d",x+i);
 rep(i,0,k) scanf("%d%d%d",a+i,b+i,c+i);
 rep(i,0,k) {
  allr.add(a[i],c[i]);
  allc.add(b[i],c[i]);
 } 

 rep(i,0,k) {
  row[i]=upper_bound(x,x+m+2,a[i])-x-1;
  col[i]=upper_bound(y,y+n+2,b[i])-y-1;
  if (x[row[i]]==a[i]&&y[col[i]]==b[i]) {
   continue;
  }
  if (x[row[i]]==a[i]) {
   segc[col[i]].add(b[i],-c[i]);
   segc[col[i]].add(y[col[i]]+y[col[i]+1]-b[i],-c[i]);
   segc[col[i]].add((ll)c[i]*(y[col[i]+1]-y[col[i]]));
   ssegc[col[i]][row[i]].add(y[col[i]]+y[col[i]+1]-b[i],c[i]);
   ssegc[col[i]][row[i]].add(-(ll)c[i]*(y[col[i]+1]-y[col[i]]));
   ssegc[col[i]][row[i]].add(b[i],c[i]);
  }
  if (y[col[i]]==b[i]) {
   segr[row[i]].add(a[i],-c[i]);
   segr[row[i]].add(x[row[i]]+x[row[i]+1]-a[i],-c[i]);
   segr[row[i]].add((ll)c[i]*(x[row[i]+1]-x[row[i]]));
   ssegr[row[i]][col[i]].add(x[row[i]]+x[row[i]+1]-a[i],c[i]);
   ssegr[row[i]][col[i]].add(-(ll)c[i]*(x[row[i]+1]-x[row[i]]));
   ssegr[row[i]][col[i]].add(a[i],c[i]);
  }
 }

 ll r1=gao(x + 1,a,c,m,k)+gao(y + 1,b,c,n,k);

 fprintf(stderr,"%lld ",r1);
 rep(i,0,k) r1=min(r1,query(a[i],b[i]));
 fprintf(stderr,"%lld\n",r1);

 printf("%lld\n",r1);
 scanf("%d",&q);
 rep(i,0,q) {
  scanf("%d%d",&xa,&ya);
  printf("%lld\n",query(xa,ya));
 }
}
详情
