Bzoj 3211(线段树/树状数组+并查集)

BZOJ 3211
2017.8.19:
本题就是线段树模板题，但是sqrt慢，并且点也只能一个个sqrt，不能一起sqrt，维护一个lazy标记区间是否全是1或0，然后写就行了(并不知道之前写的并查集是什么东西。。)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
int n, Q, data[MAXN];
int flag[MAXN * 4];
LL sumv[MAXN * 4];
#define lc (o << 1)
#define rc (o << 1 | 1)
#define M ((l + r) >> 1)
void pushup(int o) {
    sumv[o] = sumv[lc] + sumv[rc];
    flag[o] = (flag[lc] && flag[rc]);//记得传，不然TLE 
}
void build(int o, int l, int r) {
    if (l == r) {
        sumv[o] = data[l]; 
        if (sumv[o] == 0 || sumv[o] == 1) flag[o] = true;//对这个(点)开方已经没有意义 
    } else flag[o] = sumv[o] = 0, build(lc, l, M), build(rc, M + 1, r), pushup(o);
}
void update(int o, int l, int r, int x, int y) {
    if (flag[o]) return ;//这个区间都是1或0 
    if (l == r) {
        sumv[o] = sqrt(sumv[o]);
        if (sumv[o] == 0 || sumv[o] == 1) flag[o] = true;//对这个(点)开方已经没有意义 
        return ;
    }
    if (x <= M) update(lc, l, M, x, y);
    if (M < y)  update(rc, M + 1, r, x, y);
    pushup(o);
}
LL query(int o, int l, int r, int x, int y) {
    LL ret = 0;
    if (x <= l && r <= y) {
        return sumv[o];
    }
    if (x <= M) ret += query(lc, l, M, x, y);
    if (M < y)  ret += query(rc, M + 1, r, x, y);
    return ret;
}
void clean() {}
void solve() {
    clean();
    for (int i = 1; i <= n; i++) scanf("%d", &data[i]);
    build(1, 1, n);
    scanf("%d", &Q);
    while (Q--) {
        int x, l, r;
        scanf("%d%d%d", &x, &l, &r);
        if (x == 1) {
            printf("%lld\n", query(1,1,n,l,r));
        } else {
            update(1,1,n,l,r);
        }
    }
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    scanf("%d", &n), solve();
    return 0;
}

树状数组裸题，但是因为sqrt的速度很慢，所以我们在一个数为1或者为0就删掉它(用并查集维护)
ps:交题时注意文件声明部分要注释掉！坑死了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define ms(i,j) memset(i, j, sizeof i);
#define ll long long
using namespace std;
const int MAXN = 100000 + 5;
ll a[MAXN], f[MAXN];
int data[MAXN];
int n,m;
int lowbit(ll x) {return x&(-x);}
int find(int x)
{
    if (f[x]==x) return x;
    else return f[x] = find(f[x]);
}
ll sum(int x)
{
    ll ret = 0;
    for (ll i=x;i>0;i-=lowbit(i))
    {
        ret += (ll)a[i];
    }
    return ret;
}
int update(int x, int c)
{
    for (ll i=x;i<=n;i+=lowbit(i))
    {
        a[i] += c;
    }
}
int main()
{
    //freopen("bzoj3211.in", "r", stdin); freopen("bzoj3211.out", "w", stdout);
    scanf("%d\n", &n); ms(a, 0);
    for (int i=1;i<=n+1;i++) f[i] = i;
    for (int i=1;i<=n;i++) 
    {
        scanf("%lld", &data[i]);
        if (data[i]==1||data[i]==0) f[i] = find(i+1);
        update(i, data[i]); 
    }
    scanf("%d", &m);
    for (int i=1;i<=m;i++)
    {
        int x, l, r;
        scanf("%d%d%d", &x, &l, &r);
        if (x==1) printf("%lld\n", sum(r)-sum(l-1)); else if (x==2)
        {
            for (int j=find(l);j<=r;j=find(j+1))
            {
                update(j, (ll)(sqrt(data[j]))-data[j]);
                data[j] = (ll)(sqrt(data[j]));
                if(data[j]==1)
                {
                    f[j] = find(j+1);
                }
            }
        }
    }
    return 0;
}