A simple Blog for wyx I've been down the bottle hoping.
模板复习计划 欢迎各路神犇前来打脸qwq
发表于: | 分类: Oi | 评论:0 | 阅读:357

模板复习计划,争取在省选之前把所有的板子都自己打上一遍

重新写一遍发现自己的代码能力弱了不少啊……

Splay BZOJ 1500 维修数列

mgd万万没想到reverse写错了= = 调了两个小时

#include <queue>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = (500000<<1)+5;
const int inf = 0x3f3f3f3f;
int cnt, root;
#define newnode(k,V,F) k = ++cnt; sum[k] = mx[k] = lx[k] = rx[k] = val[k] = V; fa[k] = F; size[k] = 1; lazy[k] = inf
int ch[N][2], val[N], sum[N], lx[N], rx[N], mx[N], lazy[N], fa[N], size[N];
bool rev[N];

queue <int> q;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9') {x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

inline void updata(int k) {
    size[0] = val[0] = sum[0] = lx[0] = rx[0] = 0; mx[0] = -inf;
    size[k] = size[ch[k][0]] + size[ch[k][1]] + 1;
    sum[k] = sum[ch[k][0]] + sum[ch[k][1]] + val[k];
    mx[k] = max(mx[ch[k][0]], mx[ch[k][1]]);
    mx[k] = max(mx[k], rx[ch[k][0]] + val[k] + lx[ch[k][1]]);
    lx[k] = max(lx[ch[k][0]], sum[ch[k][0]] + val[k] + lx[ch[k][1]]);
    rx[k] = max(rx[ch[k][1]], sum[ch[k][1]] + val[k] + rx[ch[k][0]]);
}

inline void solve(int k) {
    rev[k] ^= 1;
    swap(ch[k][0], ch[k][1]);
    swap(lx[k], rx[k]);
}

inline void down(int k) {
    if(lazy[k] != inf) {
        int tmp = lazy[k]; lazy[k] = inf;
        lazy[ch[k][0]] = lazy[ch[k][1]] = val[ch[k][0]] = val[ch[k][1]] = tmp;
        sum[ch[k][0]] = tmp * size[ch[k][0]];
        sum[ch[k][1]] = tmp * size[ch[k][1]];
        if(tmp >= 0) {
            mx[ch[k][0]] = lx[ch[k][0]] = rx[ch[k][0]] = sum[ch[k][0]];
            mx[ch[k][1]] = lx[ch[k][1]] = rx[ch[k][1]] = sum[ch[k][1]];
        } 
        else {
            mx[ch[k][0]] = tmp;lx[ch[k][0]] = rx[ch[k][0]] = 0;
            mx[ch[k][1]] = tmp;lx[ch[k][1]] = rx[ch[k][1]] = 0;
        }
    }
    if(rev[k]) {
        rev[k] ^= 1;
        solve(ch[k][0]);
        solve(ch[k][1]);
    }
}

inline void rotate(int x) {
    int y = fa[x];
    down(y); down(x);
    int z = ch[y][1] == x;
    ch[y][z] = ch[x][!z]; fa[ch[y][z]] = y;
    ch[x][!z] = y; fa[x] = fa[y]; fa[y] = x;
    ch[fa[x]][ch[fa[x]][1] == y] = x;
    updata(y); updata(x);
}

inline void splay(int x,int w) {
    while(fa[x] != w) {
        int y = fa[x], z = fa[y];
        if(z == w) rotate(x);
        else if((ch[y][1] == x) == (ch[z][1] == y)) rotate(y), rotate(x);
        else rotate(x), rotate(x);
    }
    if(!w) root = x;
}

inline int find(int k,int rank) {
    down(k);
    int tmp = size[ch[k][0]];
    if(rank <= tmp) return find(ch[k][0], rank);
    else if(rank == tmp + 1) return k;
    else return find(ch[k][1], rank-tmp-1);
}

inline void rec(int &x) {
    if(ch[x][0]) rec(ch[x][0]);
    if(ch[x][1]) rec(ch[x][1]);
    mx[x] = size[x] = sum[x] = lx[x] = rx[x] = fa[x] = 0;
    rev[x] = false;
    lazy[x] = inf;
    q.push(x);
    x = 0;
}

int T[N];

inline void insert(int &x,int l,int r,int F) {
    if(l>r) return;
    if(!q.empty()) {x = q.front(); q.pop();}
    else x = ++cnt;
    int mid = (l+r) >> 1;
    lazy[x] = inf;
    sum[x] = mx[x] = val[x] = T[mid];
    if(T[mid] >= 0) lx[x] = rx[x] = T[mid];
    fa[x] = F; size[x] = 1;
    if(l!=r) {
        insert(ch[x][0],l,mid-1,x);
        insert(ch[x][1],mid+1,r,x);
        updata(x);
    }
//  cout << x << " " << l << " " << r << " " << mx[x] <<  " " << lx[x] << " " << rx[x] << " " << sum[x] << endl;
}

int main() {
//  freopen("tt.in","r",stdin);
//  freopen("tt.out","w",stdout);
    int n = read(), m = read();
    for(int i=1;i<=n;++i) T[i] = read();
    newnode(root, -inf, 0);
    newnode(ch[root][1], -inf, root);
    int tmp = ch[root][1];
    insert(ch[tmp][0], 1, n, tmp);
    updata(tmp); updata(root);
    char str[100];
    for(int i=1;i<=m;++i) {
        scanf("%s",str);
        if(str[0] == 'G') {
            int l = read(), r = read() + l - 1;
            splay(find(root,l),0);
            splay(find(root,r+2), root);
            int tmp = ch[root][1];
            tmp = ch[tmp][0];
            printf("%d\n", sum[tmp]);
        }
        else if(str[0] == 'I') {
            int l = read(), tot = read();
            splay(find(root,l+1), 0);
            splay(find(root,l+2),root);
            for(int i=1;i<=tot;++i) T[i] = read();
            int tmp = ch[root][1];
            insert(ch[tmp][0],1,tot,tmp);
            updata(ch[root][1]);
            updata(root);
        }
        else if(str[0] == 'R') {
            int l = read(), tot  = read();
            int r = l + tot - 1;
            splay(find(root,l),0);
            splay(find(root,r+2),root);
            int tmp = ch[root][1];
            tmp = ch[tmp][0];
            solve(tmp);
            updata(ch[root][1]);
            updata(root);
        }
        else if(str[0] == 'D') {
            int l = read(), tot = read(), r = l + tot - 1;
            splay(find(root,l),0);
            splay(find(root,r+2),root);
            int tmp = ch[root][1];
            rec(ch[tmp][0]);
            updata(tmp);
            updata(root);
        }
        else if(str[0] == 'M') {
            if(str[2] == 'X') {
                printf("%d\n", mx[root]);
            }
            else {
                int l = read(), tot = read(), r = l + tot - 1, c = read();
                splay(find(root,l),0);
                splay(find(root,r+2),root);
                int tmp = ch[root][1];
                tmp = ch[tmp][0];
                lazy[tmp] = c; 
                val[tmp] = c;
                sum[tmp] = size[tmp] * c;
                if(c >= 0) mx[tmp] = lx[tmp] = rx[tmp] = c * size[tmp];
                else {
                    lx[tmp] = rx[tmp] = 0; 
                    mx[tmp] = c;
                }
                updata(ch[root][1]);
                updata(root);
            }
        }
    //  cout << i << " " << mx[root] << endl;
    }
}

FFT

#include <cmath>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = (1<<18)+5;
typedef double f2;
const f2 PI = acos(-1);
struct cp{
    f2 a,b;
    cp (f2 _a=0,f2 _b=0):a(_a),b(_b){}
    cp operator + (const cp &z) {return cp(a+z.a,b+z.b);} 
    cp operator - (const cp &z) {return cp(a-z.a,b-z.b);}
    cp operator * (const cp &z) {return cp(a*z.a-b*z.b,a*z.b+b*z.a);}
} a[N], b[N], c[N], A[N], x, y;
 
int dig[50], rev[N], n;
 
inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9') {x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}
 
inline void FFT(cp *a,int type) { 
    register int i,j,k;
    for(i=0;i<n;++i) A[i] = a[rev[i]];
    for(i=0;i<n;++i) a[i] = A[i];
    for(i=2;i<=n;i<<=1) {
        cp wn(cos(2*PI/i),type*sin(2*PI/i));
        for(j=0;j<n;j+=i) {
            cp w(1,0);
            for(k=j;k<j+(i>>1);k++, w = w * wn) {
                x = a[k], y = a[k+(i>>1)]*w;
                a[k] = x + y, a[k+(i>>1)] = x - y;
            }
        }
    } 
    if(type == -1) for(i=0;i<n;++i) a[i].a /= n;
} 
 
int tmp1[N], tmp2[N];
int main(){
    register int i,j;
    int k = read(),l=0; k = 1<<k;
    int len = 0;
    for(i=0;i<k;++i) tmp1[i] = read();
    for(i=0;i<k;++i) tmp2[i] = read();
    for(n=1,len=0;n<=k;n<<=1,len++);
     
    for(i=0;i<n;++i,l=0) {
        for(j=i;j;j>>=1) dig[l++] = j & 1;
        for(j=0;j<len;++j) rev[i] = (rev[i]<<1) | dig[j];
    }
 
    for(i=0;i<k;++i) a[i] = cp(tmp1[i]);
    for(i=0;i<k;++i) b[i] = cp(tmp2[i]);
    FFT(a,1); 
    FFT(b,1); for(i=0;i<n;++i) c[i] = a[i]*b[i]; FFT(c,-1);
    for(i=0;i<k;++i) printf("%d\n",(int)(c[i].a+0.5));
}
 

可并堆

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100000+5;
const int M = 100000+5;
inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9') {x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}
 
struct Heap {
    Heap *ls, *rs;
    int val, h;
    Heap (int _val = 0) {
        ls = rs = NULL;
        val = _val , h = -1;
    }
    void *operator new(size_t);
}tr[M], *heap[N];
 
void * Heap :: operator new(size_t) {
    static Heap *C = tr;
    return C++;
}
 
inline Heap* merge(Heap *a, Heap *b) {
    if(a == NULL) return b;
    if(b == NULL) return a;
    if(a -> val > b -> val) swap(a,b);
    a -> rs = merge(a->rs, b);
    int tmp1 = -1, tmp2 = -1;
    if(a -> ls) tmp1 = a -> ls -> h;
    if(a -> rs) tmp2 = a -> rs -> h;
    if(tmp2 > tmp1) swap(a->ls,a->rs);
    a -> h = min(tmp1,tmp2) + 1;
    return a;
}
 
int F[N], size[N];
 
inline int find(int x) {
    return F[x] ^ x ? F[x] = find(F[x]) : F[x];
}
 
inline void Union(int x,int y) {
    int fx = find(x), fy = find(y);
    if(fx == fy) return;
    if(size[fx] < size[fy]) swap(fx,fy);
    F[fy] = fx; size[fx] += size[fy];
    heap[fx] = merge(heap[fy], heap[fx]);
}
 
int main() {
    int n = read(), m = read();
    for(int i=1;i<=n;++i) heap[i] = new Heap(i), size[F[i] = i] = 1;
    for(int i=1;i<=m;++i) {
        int opt = read();
        if(opt == 0) Union(read(),read());
        else  printf("%d\n", heap[find(read())] -> val);
    }
}

Fwt

or

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = (1<<21)+5;
int a[N], b[N], c[N];
 
__attribute__((optimize("-O2"))) char getc() {
    static const int LEN = 1<<15;
    static char buf[LEN],*S=buf,*T=buf;
    if(S == T)  {
        T = (S=buf)+fread(buf,1,LEN,stdin);
        if(S == T)return EOF;
    }
    return *S++;
}
 
__attribute__((optimize("-O2"))) int read() {
    static char ch;
    static int D;
    while(!isdigit(ch=getc())) if(ch == EOF) return -1;
    for(D=ch-'0'; isdigit(ch=getc());) D=(D<<3)+(D<<1)+(ch-'0');
    return D;
}
 
__attribute__((optimize("-O2"))) void FWT(int *a,int len,int type) {
    for(int i=1;i<len;i<<=1) {
        for(int j=0;j<len;++j) {
            if(i&j) continue;
            a[i+j] += type*a[j];
        }
    }
}
 
__attribute__((optimize("-O2"))) int main() {
    int k = read(); k = 1<<k;
    for(int i=0;i<k;++i) a[i] = read();
    for(int i=0;i<k;++i) b[i] = read();
    FWT(a,k<<1,1); FWT(b,k<<1,1);
    for(int i=0;i<(k<<1);++i) c[i] = a[i] * b[i];
    FWT(c,k<<1,-1);
    for(int i=0;i<k;++i) printf("%d\n", c[i]);
}
 

全局最小割

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 500+5;
const int inf = 0x3f3f3f3f;
inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9') {x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}
 
int mp[N][N];
int v[N], dis[N];
bool vis[N];
 
inline int solve(int n) {
    int ans = inf;
    for(int i(1);i<=n;++i) v[i] = i;
    while(n>1) {
        int k, pre = 1  ;
        memset(vis,false,sizeof vis);
        memset(dis, 0, sizeof dis);
        for(int i(2);i<=n;++i) {
            k = -1;
            for(int j(2);j<=n;++j) 
                if(!vis[v[j]]) {
                    dis[v[j]] += mp[v[pre]][v[j]];
                    if(k==-1 || dis[v[k]] < dis[v[j]]) k = j;
                }
            vis[v[k]] = 1;
            if(i==n) {
                ans = min(ans, dis[v[k]]);
                for(int j(1);j<=n;++j) {
                    mp[v[pre]][v[j]] += mp[v[j]][v[k]];
                    mp[v[j]][v[pre]] += mp[v[j]][v[k]];
                }
                v[k] = v[n--];
            }
            pre = k;
        }
    }
    return ans;
}
 
int main() {
    int n = read(), m = read();
    for(int i=1;i<=m;++i) {
        int x = read(), y = read(), z = read();
        mp[x][y] += z; mp[y][x] += z;
    }
    cout << solve(n) << endl;
}

后缀自动机 NOI2015 品酒大会

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL inf = 2e18;
const int N = 600000 +5;
const int M = N << 1;
inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9') {x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int son[N][26],depth[N], fa[N];
LL mn[N], mx[N];
int p, np, q, nq, cnt, last, size[N], root;
bool in[N];
int mp[N], a[N];

inline int newnode(int _depth){
    depth[++cnt] = _depth;
    return cnt;
}

inline void insert(int x,int node) {
    p = last, np = newnode(depth[p]+1);
    last = np; in[np] = 1; mp[np] = node;
    while(p && !son[p][x]) {
        son[p][x] = np;
        p = fa[p];
    }
    if(!p) fa[np] = root;
    else {
        q = son[p][x];
        if(depth[q] == depth[p]+1) fa[np] = q;
        else {
            int nq = newnode(depth[p]+1);
            memcpy(son[nq],son[q],sizeof son[q]);
            fa[nq] = fa[q]; fa[q] = fa[np] = nq;
            while(p && son[p][x] == q) {
                son[p][x] = nq;
                p = fa[p];
            }
        }
    }
}

int head[N];
LL ans[N], ans1[N];

struct graph {
    int next, to;
    graph () {}
    graph (int _next,int _to)
    :next(_next), to(_to) {}
}edge[M];

inline void add(int x,int y) {
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y); head[x] = cnt;
    edge[++cnt] = graph(head[y],x); head[y] = cnt;
}

inline void DFS(int x,int fa) {
    if(in[x]) {
        mx[x] = mn[x] = a[mp[x]];
        size[x] = 1;
    }
    else mx[x] = mn[x] = inf;
    for(int i=head[x];i;i=edge[i].next) {
        if(edge[i].to != fa) {
            DFS(edge[i].to,x);
            ans[depth[x]] += (LL) size[x] * size[edge[i].to];
            if(mx[x] == inf) {
                mx[x] = mx[edge[i].to];
                mn[x] = mn[edge[i].to];
            }
            else {
                ans1[depth[x]] = max(ans1[depth[x]], mx[x]*mx[edge[i].to]);
                ans1[depth[x]] = max(ans1[depth[x]], mn[x]*mn[edge[i].to]);
                mx[x] = max(mx[x], mx[edge[i].to]);
                mn[x] = min(mn[x], mn[edge[i].to]);
            }
            size[x] += size[edge[i].to];
        }
    }
}

char str[N];

int main() {
//  freopen("tt.in","r",stdin);
    int n = read();
    scanf("%s",str+1);
    last = root = newnode(0);
    reverse(str+1,str+n+1);
    for(int i=1;i<=n;++i) insert(str[i]-'a', i);
    for(int i=2;i<=cnt;++i) add(fa[i],i);
    for(int i=1;i<=n;++i) a[n-i+1] = read();
    for(int i=0;i<=n;++i) ans1[i] = -inf;
    DFS(1, -1);
    for(int i=n;i>=0;--i) ans[i] += ans[i+1];
    for(int i=n-1;i>=0;--i) ans1[i] = max(ans1[i], ans1[i+1]);
    for(int i=0;i<n;++i) 
        printf("%lld %lld\n", ans[i], ans1[i] == -inf ? 0 : ans1[i]);
}

树套树

HNOI 2017 T2 TLE

#include <set>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200000+5;
inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int n;

struct seg {
    int tmp[N*90], ls[N*90], rs[N*90], lazy[N*90], sz, root[N<<2];

    inline void down(int k,int l,int r) {
        if(!lazy[k] || l==r) return;
        int mid = (l+r) >> 1, tt = lazy[k]; lazy[k] = 0;
        if(!ls[k]) ls[k] = ++sz;
        if(!rs[k]) rs[k] = ++sz;
        lazy[ls[k]] += tt;
        lazy[rs[k]] += tt;
        tmp[ls[k]] += (mid-l+1)*tt;
        tmp[rs[k]] += (r-mid)*tt;
    }

    inline void change1(int &k,int l,int r,int x,int y,int val) {
        if(!k) k = ++sz;
        if(l==x && r==y) {
            tmp[k] += (r-l+1) * val;
            lazy[k] += val;
            return;
        }
        down(k,l,r);
        int mid = (l+r) >> 1;
        if(y <= mid) change1(ls[k],l,mid,x,y,val);
        else if(x > mid) change1(rs[k],mid+1,r,x,y,val);
        else change1(ls[k],l,mid,x,mid,val), change1(rs[k],mid+1,r,mid+1,y,val);
        tmp[k] = tmp[ls[k]] + tmp[rs[k]];
    }

    inline int ask1(int k,int l,int r,int x,int y) {
        if(!k) return 0;
        if(l==x && r==y) return tmp[k];
        down(k,l,r);
        int mid = (l+r) >> 1;
        if(y <= mid) return ask1(ls[k],l,mid,x,y);
        else if(x > mid) return ask1(rs[k],mid+1,r,x,y);
        else return ask1(ls[k],l,mid,x,mid) + ask1(rs[k],mid+1,r,mid+1,y) ;
    }

    inline void change(int k,int l,int r,int x1,int x2,int y,int val) {
        change1(root[k],1,n,x1,x2,val);
        if(l==r) return;
        int mid = (l+r) >> 1;
        if(y<=mid) change(k<<1,l,mid,x1,x2,y,val);
        else change(k<<1|1,mid+1,r,x1,x2,y,val);
    }

    inline int ask(int k,int l,int r,int x1,int y1,int x2,int y2) {
        if(l==y1 && r==y2) return ask1(root[k],1,n,x1,x2);
        int mid = (l+r) >> 1;
        if(y2 <= mid) return ask(k<<1,l,mid,x1,y1,x2,y2);
        else if(y1 > mid) return ask(k<<1|1,mid+1,r,x1,y1,x2,y2);
        else return ask(k<<1,l,mid,x1,y1,x2,mid) + ask(k<<1|1,mid+1,r,x1,mid+1,x2,y2);
    }

}tr1;

set <int> s;

struct data {
    int pos,val;
    bool operator < (const data &z) const {
        return val > z.val;
    }
} a[N];
    
int L[N], R[N], X[N], Y[N], ans[N];

int main() {
    freopen("tt.in","r",stdin);
    n = read(); int m = read(), p1 = read(), p2 = read();
    for(int i=1;i<=n;++i) a[i].pos = i, a[i].val = read();
    s.insert(0); s.insert(n+1);
    set <int> :: iterator it;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i) {
        int j=i+1;
        while(a[j].val == a[i].val) j ++; 
        j --;
        for(int k=i;k<=j;++k) s.insert(a[k].pos);
        for(int k=i;k<=j;++k) {
            it = s.upper_bound(a[k].pos); R[a[k].pos] = *it;
            it = --s.lower_bound(a[k].pos);L[a[k].pos] = *it;
        }
        for(int k=i;k<=j;++k) {
            bool flag = false;
            if(L[a[k].pos] == 0 && R[a[k].pos] == n+1) continue;
            if(L[a[k].pos] == 0) flag = true;
            if(R[a[k].pos] == n+1) flag = true;
            if(!flag) tr1.change(1,1,n,L[a[k].pos],L[a[k].pos], R[a[k].pos],p1);
            if(L[a[k].pos]+1<=a[k].pos-1 && R[a[k].pos] != n+1)tr1.change(1,1,n,L[a[k].pos]+1,a[k].pos-1,R[a[k].pos],p2);
        }
    }
    for(int i=1;i<n;++i)
        tr1.change(1,1,n,i,i,i+1,p1);
    for(int i=1;i<=m;++i) {
        X[i] = read(), Y[i] = read();
        ans[i] += tr1.ask(1,1,n, X[i], X[i], Y[i], Y[i]);
    }
    for(int i=1;i<=tr1.sz;++i) tr1.tmp[i] = tr1.lazy[i] = tr1.ls[i] = tr1.rs[i] = 0;
    for(int i=1;i<=(n<<2);++i) tr1.root[i] = 0;
    tr1.sz = 0;
    for(int i=1;i<=n;++i) 
        if(a[i].pos+1<=R[a[i].pos]-1 && L[a[i].pos] != 0) tr1.change(1,1,n,a[i].pos+1,R[a[i].pos]-1,L[a[i].pos],p2);
    for(int i=1;i<=m;++i) printf("%d\n", ans[i] + tr1.ask(1,1,n,X[i], X[i], Y[i], Y[i]));
}

主席树

HNOI2017 T2 AC

#include <set>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL N = 2e5+5;
const LL M = N << 2;
LL tr[M], lazy[M];

inline LL read() {
    LL x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

inline void down(LL k,LL l,LL r) {
    if(l==r||!lazy[k]) return;
    LL mid = (l+r) >> 1, tmp = lazy[k]; lazy[k] = 0;
    tr[k<<1] += (mid-l+1) * tmp;
    tr[k<<1|1] += (r-mid) * tmp;
    lazy[k<<1] += tmp;
    lazy[k<<1|1] += tmp;
    return;
}

inline void change(LL k,LL l,LL r,LL x,LL y,LL val) {
    if(l==x && r==y) {
        tr[k] += (r-l+1)*val;
        lazy[k] += val;
        return;
    }
    down(k,l,r);
    LL mid = (l+r) >> 1;
    if(y <= mid) change(k<<1,l,mid,x,y,val);
    else if(x > mid) change(k<<1|1,mid+1,r,x,y,val);
    else change(k<<1,l,mid,x,mid,val), change(k<<1|1,mid+1,r,mid+1,y,val);
    tr[k] = tr[k<<1] + tr[k<<1|1];
}

inline LL ask(LL k,LL l,LL r,LL x,LL y) {
    if(l==x && r==y) return tr[k];
    down(k,l,r);
    LL mid = (l+r) >> 1;
    if(y <= mid) return ask(k<<1,l,mid,x,y);
    else if(x > mid) return ask(k<<1|1,mid+1,r,x,y);
    else return ask(k<<1,l,mid,x,mid) + ask(k<<1|1,mid+1,r,mid+1,y);
}

struct line {
    LL x1,x2,y,val,opt,id;
    bool operator < (const line &z) const {
        if(y != z.y) return y < z.y;
        return opt < z.opt;
    }
} l[N<<4];

set <LL> s;

struct data {
    LL pos,val;
    bool operator < (const data &z) const {
        return val > z.val;
    }
} a[N];
    
LL L[N], R[N], X[N], Y[N], ans[N], top;

int main() {
//  freopen("tt.in","r",stdin);
    LL n = read(); LL m = read(), p1 = read(), p2 = read();
    for(LL i=1;i<=n;++i) a[i].pos = i, a[i].val = read();
    s.insert(0); s.insert(n+1);
    set <LL> :: iterator it;
    sort(a+1,a+n+1);
    for(LL i=1;i<=n;++i) {
        LL j=i+1;
        while(a[j].val == a[i].val) j ++; 
        j --;
        for(LL k=i;k<=j;++k) s.insert(a[k].pos);
        for(LL k=i;k<=j;++k) {
            it = s.upper_bound(a[k].pos); R[a[k].pos] = *it;
            it = --s.lower_bound(a[k].pos);L[a[k].pos] = *it;
        }
        for(LL k=i;k<=j;++k) {
            bool flag = false;
            if(L[a[k].pos] == 0 && R[a[k].pos] == n+1) continue;
            if(L[a[k].pos] == 0) flag = true;
            if(R[a[k].pos] == n+1) flag = true;
            if(!flag) l[++top] = (line){L[a[k].pos],L[a[k].pos], R[a[k].pos],p1,0,0};
            if(L[a[k].pos]+1<=a[k].pos-1 && R[a[k].pos] != n+1) l[++top] = (line){L[a[k].pos]+1, a[k].pos-1, R[a[k].pos], p2, 0, 0};
        }
    }
    for(LL i=1;i<=m;++i) X[i] = read(), Y[i] = read();
    for(LL i=1;i<=m;++i) {
        l[++top] = (line){X[i], Y[i], X[i]-1,0,1,i};
        l[++top] = (line){X[i], Y[i], Y[i] , 0,2,i};
    }
    for(LL i=1;i<n;++i) l[++top] = (line){i,i,i+1,p1,0,0};
    sort(l+1,l+top+1);
    for(LL i=1;i<=top;++i) {
        if(l[i].opt==0) change(1,0,n+1,l[i].x1,l[i].x2,l[i].val);
        else if(l[i].opt==1) ans[l[i].id] -= ask(1,0,n+1,l[i].x1,l[i].x2);
        else ans[l[i].id] += ask(1,0,n+1,l[i].x1,l[i].x2);
    }

    top = 0;
    memset(tr,0,sizeof tr);
    memset(lazy,0,sizeof lazy);
    for(LL i=1;i<=m;++i) {
        l[++top] = (line){X[i], Y[i],X[i]-1, 0, 1, i};
        l[++top] = (line){X[i], Y[i],  Y[i], 0, 2, i};
    }
    for(LL i=1;i<=n;++i) 
        if(a[i].pos+1<=R[a[i].pos]-1 && L[a[i].pos] != 0) l[++top] = (line){a[i].pos+1,R[a[i].pos]-1,L[a[i].pos],p2,0,0};
    sort(l+1,l+top+1);
//  for(LL i=1;i<=top;++i) cout << l[i].x1 << " " << l[i].x2 << " " << l[i].y  << " " << l[i].id << endl; 
    for(LL i=1;i<=top;++i) {
        if(l[i].opt==0) change(1,0,n+1,l[i].x1,l[i].x2,l[i].val);
        else if(l[i].opt==1) ans[l[i].id] -= ask(1,0,n+1,l[i].x1,l[i].x2);
        else ans[l[i].id] += ask(1,0,n+1,l[i].x1,l[i].x2);
    }
    for(LL i=1;i<=m;++i) printf("%lld\n", ans[i]);
}


杜教筛

BZOJ 4805

#include <map>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL N = 1e7+5;
map <LL,LL> mp;

inline LL read() {
    LL x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9') {x = (x<<1) + (x<<3) + ch - '0'; ch = getchar();}
    return x*f;
}

LL prime[N], cnt;
LL phi[N];
bool F[N];

inline void init() {
    const LL Max = 1e7;
    register LL j;
    phi[1] = 1;
    for(LL i=2;i<=Max;++i) {
        if(!F[i]) prime[++cnt] = i, phi[i] = i-1;
        for(j=1;prime[j]*i<=Max;++j) {
            F[i*prime[j]] = 1;
            if(i%prime[j]==0) {
                phi[prime[j]*i] = prime[j]*phi[i];
                break;
            }
            phi[prime[j]*i] = (prime[j]-1)*phi[i];
        }
    }
    for(LL i=2;i<=Max;++i) phi[i] += phi[i-1];
}

inline LL calc(LL n) {
    LL last;
    static const LL Max = 1e7;
    if(n <= Max) return phi[n];
    else if(mp.count(n)) return mp[n];
    LL tmp1 = (n)*(n+1)/2;
    for(LL i=2;i<=n;i=last+1) {
        last = n/(n/i);
    //  cout << calc(n/i) << endl;
        tmp1 -= (LL)(last-i+1)*calc(n/i);
    }
    return (mp[n] = tmp1);
}

int main() {
//  freopen("tt.in","r",stdin);
//  freopen("tt.out","w",stdout);
    init();
    LL n = read();
    cout << calc(n);
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP