Solved:3

Rank:105

治哥出题了 我感动哭了

A Graph Game (分块)

题意:1e5个点 2e5条边 s(x)表示与x点直接相邻的点集合

　　 有两种操作 1种将按输入顺序的边第l条到第r条边翻转 连接->切断 切断->链接

　　 还有一种询问 s(x)与s(y)是否相等

题解:题解说 可以给每个点随机一个值 然后s(x)可以用与x直接相邻的点xor起来 (还有这种操作???

　　 然后我们把边分块 翻转操作就是xor操作 每个点之间边的状态是一样的 所以可以共用

　　 而且对一条边的修改 影响的只有两个点的信息 所以对块两边的边暴力修改他所影响的点

#include
using namespace std;
const int MAXN = 1e5 + 5;

int n, m, blo;
int bl[MAXN << 1];
int sum[MAXN][505];
int now[MAXN];
int val[MAXN];
int u[MAXN << 1];
int v[MAXN << 1];
int vis[505];

void update(int l, int r) {
for(int i = l; i <= min(r, bl[l] * blo); i++) {
now[u[i]] ^= val[v[i]];
now[v[i]] ^= val[u[i]];
}

if(bl\[l\] != bl\[r\]) {  
    for(int i = (bl\[r\] - 1) \* blo + 1; i <= r; i++) {  
        now\[u\[i\]\] ^= val\[v\[i\]\];  
        now\[v\[i\]\] ^= val\[u\[i\]\];  
    }  
}  
for(int i = bl\[l\] + 1; i < bl\[r\]; i++) vis\[i\] ^= 1;  

}

int main() {
srand(time(NULL));
for(int i = 1; i <= 100000; i++) val[i] = rand() + 1;

int T;  
scanf("%d", &T);  
while(T--) {  
    scanf("%d%d", &n, &m);  
    blo = sqrt(m);  
    for(int i = 1; i <= m; i++) bl\[i\] = (i - 1) / blo + 1;  
    for(int i = 1; i <= n; i++) now\[i\] = 0;  
    for(int i = 1; i <= n; i++)  
    for(int j = 1; j <= bl\[m\]; j++) sum\[i\]\[j\] = 0;  
    for(int i = 1; i <= bl\[m\]; i++) vis\[i\] = 1;

    for(int i = 1; i <= m; i++) {  
        scanf("%d%d", &u\[i\], &v\[i\]);  
        sum\[u\[i\]\]\[bl\[i\]\] ^= val\[v\[i\]\];  
        sum\[v\[i\]\]\[bl\[i\]\] ^= val\[u\[i\]\];  
    }

    int qu; scanf("%d", &qu);  
    while(qu--) {  
        int opt, x, y;  
        scanf("%d%d%d", &opt, &x, &y);  
        if(opt == 1) update(x, y);  
        else if(opt == 2) {  
            int ans1 = now\[x\], ans2 = now\[y\];  
            for(int i = 1; i <= bl\[m\]; i++) {  
                if(vis\[i\]) {  
                    ans1 ^= sum\[x\]\[i\];  
                    ans2 ^= sum\[y\]\[i\];  
                }  
            }  
            if(ans1 == ans2) printf("1");  
            else printf("0");  
        }  
    }  
    puts("");  
}  
return 0;  

}

A Graph Game

F Planting Trees

题意:500x500的矩阵 求一个最大的子矩阵 使得区间最大减最小<=M

题解:枚举纵坐标的区间 对于每一个区间 从第一行开始 单调尺取搞一搞

#include
using namespace std;

int a[505][505];
int zd[505];
int zx[505];

int qd[505];
int qx[505];

int main() {
int T;
scanf("%d", &T);
while(T--) {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
}

    int ans = 1;  
    for(int j = 1; j <= n; j++) {  
        for(int k = 1; k <= n; k++) {  
            zx\[k\] = 1e5 + 5;  
            zd\[k\] = 0;  
        }  
        for(int k = j; k <= n; k++) {  
            for(int i = 1; i <= n; i++) {  
                zd\[i\] = max(zd\[i\], a\[i\]\[k\]);  
                zx\[i\] = min(zx\[i\], a\[i\]\[k\]);  
            }

            int lx = 1, rx = 0;  
            int ld = 1, rd = 0;

            int nowl = 1;  
            for(int i = 1; i <= n; i++) {  
                while(lx <= rx && zx\[qx\[rx\]\] >= zx\[i\]) rx--;  
                qx\[++rx\] = i;  
                while(ld <= rd && zd\[qd\[rd\]\] <= zd\[i\]) rd--;  
                qd\[++rd\] = i;

                while(nowl <= i && zd\[qd\[ld\]\] - zx\[qx\[lx\]\] > m) {  
                    nowl++;  
                    while(lx <= rx && qx\[lx\] < nowl) lx++;  
                    while(ld <= rd && qd\[ld\] < nowl) ld++;  
                }  
                if(nowl <= i && zd\[qd\[ld\]\] - zx\[qx\[lx\]\] <= m) {  
                    ans = max(ans, (k - j + 1) \* (i - nowl + 1));  
                }  
            }  
        }  
    }  
    printf("%d\\n", ans);  
}  
return 0;  

}

F Planting Trees

G Removing Stones

题意:n堆石子 每次可以选择两堆不同的各拿走一个 如果能拿完 就表示获胜

　　 如果石子的和为奇数 则将最少的一堆石子数-1

　　 问有多少对区间 能获胜

题解:显然 题目等于 计算 区间max * 2 <= 区间和的个数

　　 考虑反问题 计算max * 2 > 区间和

　　 然后直接暴力枚举每个点作为最大值 往前搞搞 往后搞搞

　　 巧妙的是这样的时间复杂度其实并不高 要让这样暴力枚举的时间复杂度退化到n方的数据 显然是ai >= ai+1  * 2
　　 举个例子长度为5的数组 16 8 4 2 1 能让暴力枚举的复杂度退化到n方 但是ai < 1e9

　　 均摊一下每个数的平均枚举到log

#include
using namespace std;
typedef long long ll;
ll a[300005];
ll pre[300005];

int main() {
int T;
scanf("%d", &T);
while(T--) {
ll n;
scanf("%lld", &n);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);

    ll ans = 0;  
    for(int i = 1; i <= n; i++) {  
        int cnt = 0;  
        pre\[0\] = 0;  
        for(int j = i + 1; j <= n; j++) {  
            pre\[++cnt\] = a\[j\];  
            pre\[cnt\] += pre\[cnt - 1\];  
            if(pre\[cnt\] >= a\[i\]) {  
                cnt--;  
                break;  
            }  
        }

        ans += cnt;  
        ll sum = 0;  
        for(int j = i - 1; j >= 1; j--) {  
            sum += a\[j\];  
            if(sum >= a\[i\]) break;

            ans++;  
            int l = 0, r = cnt;  
            int mid = l + r >> 1;  
            while(l + 1 < r) {  
                mid = l + r >> 1;  
                if(sum + pre\[mid\] < a\[i\]) l = mid;  
                else r = mid;  
            }  
            if(sum + pre\[r\] < a\[i\]) ans += r;  
            else ans += l;  
        }  
    }

    ans = n \* (n - 1) / 2 - ans;  
    printf("%lld\\n", ans);  
}

return 0;  

}

G Removing Stones