danihao123's Blog

aji波兰题！（迫真）

啊波兰题真好康（一转）

考虑怎么去除非加油站的影响……对于每两个加油站，取他们的最短路，然后建出来一个图，这个图的MST上的路径的走法就事最优走法。

但这样显然会凉……因为\(s\)肥肠巨大，会T。然后我们考虑多源最短路，并且给每个点标记到它最近的加油站（称为来源）。那么考虑两条加油站间的路径，上面一定有一条边满足边两个端点不一样（证明考虑……如果所有边两边端点的来源都一样，那么所有边的来源会同时事那两个加油站）。

然后一个小问题事，如果一个点有多个来源，只考虑一个会出事吗？这个事不会的。比如说有三个加油站\(a\)、\(b\)、\(c\)，如果说三者到一个点的最短路都一样，那么我们考虑只取\(a\)。如果\(b\)和\(c\)本来能连一条边，但现在因为这个连不了了，那他们还是能同时各和\(a\)连一条长度和原来的那条边长度一样的边，所以事实上没有什么笋丝。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
const int maxn = 200005, maxm = 400005;
int first[maxn];
int next[maxm], to[maxm], dist[maxm];
bool dir[maxm];
void add_edge(int u, int v, int w, bool d = true) {
  static int cnt = 0;
  cnt ++; next[cnt] = first[u]; first[u] = cnt;
  to[cnt] = v; dist[cnt] = w; dir[cnt] = d;
}
void ins_edge(int u, int v, int w) {
  add_edge(u, v, w); add_edge(v, u, w, false);
}

using ll = long long;
using pii = std::pair<ll, int>;
int n; std::vector<int> V;
ll d[maxn]; int src[maxn];
bool vis[maxn];
void dij() {
  memset(d, 0x1f, sizeof(d));
  std::priority_queue<pii, std::vector<pii>, std::greater<pii> > Q;
  for(auto p : V) {
    d[p] = 0; src[p] = p;
    Q.push(std::make_pair(0LL, p));
  }
  while(!Q.empty()) {
    int u = Q.top().second; Q.pop();
    if(vis[u]) continue;
    vis[u] = true;
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(d[u] + (ll(dist[i])) < d[v]) {
        d[v] = d[u] + (ll(dist[i]));
        src[v] = src[u];
        Q.push(std::make_pair(d[v], v));
      }
    }
  }
}

int p[maxn], rk[maxn];
int get_fa(int x) {
  if(p[x] == x) {
    return x;
  } else {
    return (p[x] = get_fa(p[x]));
  }
}
void link_set(int x, int y) {
  if(rk[x] > rk[y]) std::swap(x, y);
  p[x] = y;
  if(rk[x] == rk[y]) rk[y] ++;
}
void merge_set(int x, int y) {
  x = get_fa(x); y = get_fa(y);
  if(x != y) link_set(x, y);
}
bool is_same(int x, int y) {
  return (get_fa(x) == get_fa(y));
}
void init_set() {
  for(int i = 1; i <= n; i ++) {
    p[i] = i;
  }
}

struct Edge {
  int u, v; ll w;
  Edge(int a = 0, int b = 0, ll c = 0) {
    u = a; v = b; w = c;
  }
  bool operator <(const Edge &res) const {
    return w < res.w;
  }
};
int m; Edge E[maxm];
int ecnt;
void process() {
  dij(); ecnt = 0;
  for(int i = 1; i <= n; i ++) {
    for(int j = first[i]; j; j = next[j]) {
      int v = to[j];
      if(dir[j] && src[i] != src[v]) {
        E[++ ecnt] = Edge(src[i], src[v], (ll(dist[j])) + d[i] + d[v]);
      }
    }
  }
  std::sort(E + 1, E + 1 + ecnt);
}
bool ans[maxm];
void solve() {
  int q; scanf("%d", &q);
  init_set(); int cur = 0;
  std::vector<std::pair<Edge, int> > Q;
  for(int i = 1; i <= q; i ++) {
    int u, v; ll w; scanf("%d%d%lld", &u, &v, &w);
    Q.push_back(std::make_pair(Edge(u, v, w), i));
  }
  std::sort(Q.begin(), Q.end());
  for(auto x : Q) {
    Edge e = x.first;
    while(cur < ecnt && E[cur + 1].w <= e.w) {
      cur ++;
      merge_set(E[cur].u, E[cur].v);
    }
    ans[x.second] = is_same(e.u, e.v);
  }
  for(int i = 1; i <= q; i ++) {
    if(ans[i]) {
      puts("TAK");
    } else {
      puts("NIE");
    }
  }
}

int main() {
  int s; scanf("%d%d%d", &n, &s, &m);
  for(int i = 1; i <= s; i ++) {
    int x; scanf("%d", &x);
    V.push_back(x);
  }
  for(int i = 1; i <= m; i ++) {
    int u, v, w; scanf("%d%d%d", &u, &v, &w);
    ins_edge(u, v, w);
  }
  process(); solve();
  return 0;
}

CDQ分治第一题……同时也是CDQ分治模板提。

感觉CDQ分治思路好秒啊……似乎在分治过程中做了个归并排序……

代码：

/**************************************************************
    Problem: 1176
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4364 ms
    Memory:17228 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxw=2000005;
const int maxq=10005;
const int maxn=160001+4*maxq;
int cnt=0;
struct Query{
  int ans_id;
  int x,y,d,v;
  Query(){}
  Query(int a,int b,int di,int ap){
    x=a;y=b;
    d=di;
    ans_id=ap;
  }
  Query(int a,int b,int value){
    x=a;y=b;
    v=value;
    d=0;
  }
  inline bool isQuery(){
    return d!=0;
  }
};
 
int w;
int T[maxw];
inline int lowbit(int x){
  return x&(-x);
}
inline void add(int p,int v){
  while(p<=w){
    T[p]+=v;
    p+=lowbit(p);
  }
}
inline int sum(int p){
  register int x=0;
  while(p>0){
    x+=T[p];
    p-=lowbit(p);
  }
  return x;
}
inline void clear(int p){
  while(p<=w && T[p]!=0){
    T[p]=0;
    p+=lowbit(p);
  }
}
 
Query Q[maxn],tmp[maxn];
int ans[maxn];
void CDQ(int L,int R){
  if(L==R){
    return;
  }
  int M=L+(R-L)/2;
  CDQ(L,M);
  CDQ(M+1,R);
  int p,p1,p2;
  for(p=1,p1=L,p2=M+1;p<=(R-L+1);p++){
    if((Q[p1].x<=Q[p2].x && p1<=M) || p2>R){
      tmp[p]=Q[p1];
      if(!Q[p1].isQuery()){
        add(Q[p1].y,Q[p1].v);
      }
      p1++;
    }else{
      tmp[p]=Q[p2];
      if(Q[p2].isQuery()){
        ans[Q[p2].ans_id]+=sum(Q[p2].y)*Q[p2].d;
      }
      p2++;
    }
  }
  for(p=1,p1=L;p<=(R-L+1);p++,p1++){
    if(!Q[p1].isQuery()){
      clear(Q[p1].y);
    }
    Q[p1]=tmp[p];
  }
}
 
int main(){
  int S,t,x,y,a,b;
  register int ans_cnt=0;
  scanf("%d%d",&S,&w);
  while(true){
    scanf("%d",&t);
    if(t==3){
      break;
    }
    scanf("%d%d%d",&x,&y,&a);
    // x++;y++;
    if(t==1){
      Q[++cnt]=Query(x,y,a);
    }else{
      scanf("%d",&b);
      // a++;b++;
      ans_cnt++;
      ans[ans_cnt]=(a-x+1)*(b-y+1)*S;
      Q[++cnt]=Query(a,b,1,ans_cnt);
      Q[++cnt]=Query(x-1,b,-1,ans_cnt);
      Q[++cnt]=Query(a,y-1,-1,ans_cnt);
      Q[++cnt]=Query(x-1,y-1,1,ans_cnt);
    }
  }
  CDQ(1,cnt);
  for(register int i=1;i<=ans_cnt;i++){
    printf("%d\n",ans[i]);
  }
  return 0;
}

今年第一更……噫

终于学会莫队了，不过目前只能做这样的模板题……

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <utility>
using namespace std;
const int maxn=50005;
typedef long long ll;
ll gcd(ll a,ll b){
    if(!b){
        return a;
    }else{
        return gcd(b,a%b);
    }
}
ll C2(ll n){
    register ll temp,ns1=n-1;
    if(n&1){
        temp=ns1>>1;
        return temp*n;
    }else{
        temp=n>>1;
        return temp*ns1;
    }
}
 
struct Node{
    int L_s;
    int L,R;
    int id;
    ll ans1,ans2;
};
bool cmp1(const Node& a,const Node& b){
    if(a.L_s==b.L_s){
        return a.R<b.R;
    }else{
        return a.L_s<b.L_s;
    }
}
bool cmp2(const Node& a,const Node& b){
    return a.id<b.id;
}
Node Q[maxn];
int C[maxn],d[maxn];
int n,m;
inline void add_p(int x,ll &ans){
    d[x]++;
    ans+=d[x]-1;
}
inline void sub_p(int x,ll &ans){
    d[x]--;
    ans-=d[x];
}
inline void Mo(){
    register int i,j,L_p,R_p,sqrt_n=sqrt(n+0.5);
    register ll ans,t_gcd,t2;
    for(i=1;i<=m;i++){
        Q[i].L_s=Q[i].L/sqrt_n;
    }
    sort(Q+1,Q+1+m,cmp1);
    L_p=R_p=Q[1].L;
    ans=0;
    d[C[L_p]]++;
    for(i=1;i<=m;i++){
        while(L_p<Q[i].L){
            sub_p(C[L_p],ans);
            L_p++;
        }
        while(L_p>Q[i].L){
            L_p--;
            add_p(C[L_p],ans);
        }
        while(R_p<Q[i].R){
            R_p++;
            add_p(C[R_p],ans);
        }
        while(R_p>Q[i].R){
            sub_p(C[R_p],ans);
            R_p--;
        }
        t2=C2(R_p-L_p+1);
        t_gcd=gcd(ans,t2);
        Q[i].ans1=ans/t_gcd;
        Q[i].ans2=t2/t_gcd;
    }
    sort(Q+1,Q+1+m,cmp2);
}
 
int main(){
    register int i;
    int a,b;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&C[i]);
    }
    for(i=1;i<=m;i++){
        Q[i].id=i;
        scanf("%d%d",&a,&b);
        Q[i].L=a;
        Q[i].R=b;
    }
    Mo();
    for(i=1;i<=m;i++){
        printf("%lld/%lld\n",Q[i].ans1,Q[i].ans2);
    }
    return 0;
}

扫描线处女作TAT

直接离线，按左端点排序扫描。每个点要保存后继相同节点，每种元素第一次出现的位置都加1。然后扫描的时候有后继就给后继加。之后求区间和即可。

代码：

/**************************************************************
    Problem: 1878
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1344 ms
    Memory:8444 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=50001,maxm=200001;
int T[maxn];
int n;
inline int lowbit(int x){
    return x&(-x);
}
inline void update(int p,int v){
    while(p<=n){
        T[p]+=v;
        p+=lowbit(p);
    }
}
inline int query(int p){
    register int ans=0;
    while(p>0){
        ans+=T[p];
        p-=lowbit(p);
    }
    return ans;
}
 
struct Query{
    int l,r;
    int id;
    int ans;
    bool operator <(const Query& x) const{
        return l==x.l?r<x.r:l<x.l;
    }
};
Query Q[maxm];
bool cmp2(const Query& a,const Query& b){
    return a.id<b.id;
}
 
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[10];
inline void writeint(int x){
    register int p=0;
    if(x==0){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(register int i=p-1;i>=0;i--)
        putchar('0'+bf[i]);
}
 
int next[maxn];
int A[maxn];
int pos[1000001];
int main(){
    int m,maxA=0;
    register int i,j;
    n=readint();
    for(i=1;i<=n;i++){
        A[i]=readint();
        maxA=max(maxA,A[i]);
    }
    for(i=n;i;i--){
        next[i]=pos[A[i]];
        pos[A[i]]=i;
    }
    for(i=1;i<=maxA;i++)
        if(pos[i])
            update(pos[i],1);
    m=readint();
    for(i=1;i<=m;i++){
        Q[i].l=readint();
        Q[i].r=readint();
        Q[i].id=i;
    }
    sort(Q+1,Q+1+m);
    register int tot=1;
    for(i=1;i<=m;i++){
        while(tot<Q[i].l){
            if(next[tot])
                update(next[tot],1);
            tot++;
        }
        Q[i].ans=query(Q[i].r)-query(Q[i].l-1);
    }
    sort(Q+1,Q+1+m,cmp2);
    for(i=1;i<=m;i++){
        writeint(Q[i].ans);
        putchar('\n');
    }
    return 0;
}

这道题到现在才A……

其实……离线处理并不像我想的那样变态……

需要注意的是，离线处理过程中，在将被删除的点加入时，联通分量数可能增加（其他一个点都连不了）

代码：