Starry

发表于 更新于 分类于 本文字数： 348 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

ll n,m,fk[(int)1e5+9],tag[(int)1e5+9],kc,bl[(int)1e5+9],a[(int)1e5+9];
 
void change(int l,int r){
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i)a[i]^=1,fk[bl[l]]+=a[i]==1?1:-1;
		return ;
	}
	int st=bl[l]+1,en=bl[r]-1;
	for(int i=st;i<=en;++i)tag[i]^=1;
	for(int i=l;i<st*kc;++i)a[i]^=1,fk[bl[l]]+=a[i]==1?1:-1;
	for(int i=bl[r]*kc;i<=r;++i)a[i]^=1,fk[bl[r]]+=a[i]==1?1:-1;
}

int query(int l,int r){
	int res=0;
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i)res+=a[i]^tag[bl[r]];
		return res;
	}
	int st=bl[l]+1,en=bl[r]-1;
	for(int i=st;i<=en;++i)res+=tag[i]?kc-fk[i]:fk[i];
	for(int i=l;i<st*kc;++i)res+=a[i]^tag[bl[l]];
	for(int i=bl[r]*kc;i<=r;++i)res+=a[i]^tag[bl[r]];
	return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    kc=sqrt(n);
    for(int i=1;i<=n;++i)bl[i]=i/kc;

    for(int i=1,opt,l,r;i<=m;++i){
    	cin>>opt>>l>>r;
    	if(!opt)change(l,r);
    	else cout<<query(l,r)<<"\n";
    }
    return 0;
}

发表于 更新于 分类于 本文字数： 395 阅读时长 ≈ 1 分钟

预处理每个点所属块序号减少常数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

ll n,m,kk,a[(int)2e5+9],fk[(int)2e5+9],tag[(int)2e5+9],bl[(int)2e5+9]; 


void update(int l,int r,int x){
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i)a[i]+=x,fk[bl[i]]+=x;
		return ;
	}
	int st=bl[l]+1,en=bl[r]-1;
	for(int i=st;i<=en;++i)tag[i]+=x;
	for(int i=l;i<st*kk;++i)a[i]+=x,fk[bl[i]]+=x;
	for(int i=en*kk+kk;i<=r;++i)a[i]+=x,fk[bl[i]]+=x;
}

ll query(int l,int r){
	ll res=0;
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i)res+=a[i];
		res+=(r-l+1ll)*tag[l/kk];
		return res;
	}
	int st=bl[l]+1,en=bl[r]-1;
	for(int i=st;i<=en;++i)res+=kk*tag[i]+fk[i];
	for(int i=l;i<st*kk;++i)res+=a[i]+tag[bl[i]];
	for(int i=en*kk+kk;i<=r;++i)res+=a[i]+tag[bl[i]];
	return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    kk=sqrt(n)+0.5;
    f(i,1,n)cin>>a[i],fk[i/kk]+=a[i],bl[i]=i/kk;
    for(int i=1,opt,l,r,k;i<=m;++i){
    	cin>>opt;
    	if(opt==1){
    		cin>>l>>r>>k;
    		update(l,r,k);
    	}else if(opt==2){
    		cin>>k;
    		update(1,1,k);
    	}else if(opt==3){
    		cin>>k;
    		update(1,1,-k);
    	}else if(opt==4){
    		cin>>l>>r;
    		cout<<query(l,r)<<"\n";
    	}else cout<<query(1,1)<<"\n";
    }
    return 0;
}

发表于 更新于 分类于 本文字数： 217 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

ll n,a[(int)1e4+9],dp[(int)1e4+9][2];
vi g[(int)1e4+9];
bitset<(int)1e4+9> ez;

void dfs(int u){
	dp[u][0]=0,dp[u][1]=a[u];
	for(auto it:g[u]){
		dfs(it);
		dp[u][0]+=max(dp[it][1],dp[it][0]),dp[u][1]+=dp[it][0];
	}
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    f(i,1,n)cin>>a[i];
    for(int i=2,x,y;i<=n;++i){
    	cin>>x>>y;
    	g[y].push_back(x);
    	ez[x]=1;
    }
    f(i,1,n){
    	if(!ez[i]){
    		dfs(i);
    		cout<<max(dp[i][0],dp[i][1]);
    		return 0;
    	}
    }
    return 0;
}

发表于 更新于 分类于 本文字数： 560 阅读时长 ≈ 2 分钟

卡时间过了 ^_^

卡时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;

using ll=long long;

const int mod=998244353;
const int g=3,gi=332748118,NR=1<<19,maxn=125009;

int n=1,m,a[NR],b[NR],tot,rev[NR],bit,ans[10][10][maxn],ls,lt,sig;
bitset<300> vis;
char s[maxn],t[maxn];
vector<char> sigma;

struct dsu{
	vector<int> fa,sz;
	dsu(int x){
		fa.resize(x+1),sz.resize(x+1);
		for(int i=1;i<=x;++i)fa[i]=i,sz[i]=1;
	}
	int fnd(int x){return x==fa[x]?x:fa[x]=fnd(fa[x]);}
	bool merge(int x,int y){
		int oa=fnd(x),ob=fnd(y);
		if(oa!=ob){
			fa[ob]=oa,sz[oa]+=sz[ob];
			return true;
		}
		return false;
	}
};

int powmod(int a,int b){
	int res=1;
	for(;b>0;b>>=1,a=1ll*a*a%mod)if(b&1)res=1ll*res*a%mod;
	return res;
}

void NTT(int *a,int type){
	for(int i=0;i<n;++i)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int i=1;i<n;i<<=1){
		int gn=powmod(type?g:gi,(mod-1)/(i<<1));
		for(int j=0;j<n;j+=(i<<1)){
			ll g0=1;
			for(int k=0;k<i;++k,g0=1ll*g0*gn%mod){
				int x=a[j+k],y=g0*a[i+j+k]%mod;
				a[j+k]=(x+y)%mod,a[i+j+k]=(x-y+mod)%mod;
			}
		}
	}
	if(type==1)return ;
	int invn=powmod(n,mod-2);
	for(int i=0;i<n;++i)a[i]=1ll*a[i]*invn%mod;
}

void solve(char aa,char bb){
	//printf("%c--%c\n",aa,bb);
	for(int i=0;i<n;++i)a[i]=b[i]=0;
	for(int i=1;i<=ls;++i)a[i-1]=(s[i]==aa);
	for(int j=1;j<=lt;++j)b[lt-j]=(t[j]==bb);
	//for(int i=0;i<ls;++i)cout<<a[i]<<" \n"[i==ls-1];\
	for(int i=0;i<lt;++i)cout<<b[i]<<" \n"[i==lt-1];
	NTT(a,1),NTT(b,1);
	for(int i=0;i<n;++i)a[i]=1ll*b[i]*a[i]%mod;
	NTT(a,0);
	for(int i=lt-1;i<ls;++i)ans[aa-'a'][bb-'a'][i]=a[i]!=0;
}

int cal(int x){
	//cerr<<x<<"---\n";
	dsu d(30);
	int res=0;
	for(int i=0;i<sig;++i)for(int j=0;j<sig;++j)if(ans[sigma[i]-'a'][sigma[j]-'a'][x])res+=d.merge(sigma[i]-'a',sigma[j]-'a');
	return res;
}

int main(){
	scanf("%s%s",s+1,t+1);
	ls=strlen(s+1),lt=strlen(t+1);
	for(int i=1;i<=ls;++i)if(!vis[s[i]])sigma.push_back(s[i]),vis[s[i]]=1;
	for(int i=1;i<=lt;++i)if(!vis[t[i]])sigma.push_back(t[i]),vis[t[i]]=1;
	sig=sigma.size();
	while(n<ls+lt)n<<=1,bit+=1;
	for(int i=0;i<n;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
	for(int i=0;i<sig;++i){
		for(int j=0;j<sig;++j){
			if(i==j)continue;
			solve(sigma[i],sigma[j]);
		}
	}
	for(int i=lt-1;i<ls;++i)printf("%d%c",cal(i)," \n"[i==ls-1]);
}

发表于 更新于 分类于 本文字数： 952 阅读时长 ≈ 3 分钟

最近霉运连连，微信消息no response搞得去蹭曾老师的球台vp，QQ因为某事炸号

E题主要是先树链剖分，然后像吉司机线段树那样对一些有规律的区间进行标记，减少操作数。

莫比乌斯函数打表发现最多加一次就可以到达的循环中或者直接对应的莫比乌斯函数值为0即：

code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <bits/stdc++.h>

using namespace std;

using ll=long long;

ll n,q, a[(int)1e6+9],M,p[(int)4e6+9],dep[(int)1e5+9],sz[(int)1e5+9],top[(int)1e5+9],son[(int)1e5+9],f[(int)1e5+9],id[(int)1e5+9],cov[(int)1e5+9];
bitset<(int)5e6+900> vis;
int mu[(int)5e6+900],pr[(int)5e6+900],cnt,tot;

const int maxn=1e5+9;
struct Node{
    int l,r,tag,cs;
    ll v;
}tr[maxn<<2];
bitset<(maxn*4ll)> upd;

void build(int l,int r,int tot){
    if(l==r){
        tr[tot].v=a[cov[l]];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,tot<<1),build(mid+1,r,(tot<<1)|1);
    tr[tot].v=tr[tot<<1].v+tr[(tot<<1)|1].v;
}

void update(int nl,int nr,int tot,int l,int r){
    int mid=(nl+nr)>>1;
    if(tr[tot].cs&&nl!=nr){
        tr[tot<<1].v+=tr[tot<<1].tag*(tr[tot].cs&1?1ll:0ll),tr[tot<<1|1].v+=tr[tot<<1|1].tag*(tr[tot].cs&1?1ll:0ll);
        tr[tot<<1].cs+=tr[tot].cs,tr[(tot<<1)|1].cs+=tr[tot].cs;
        tr[tot<<1].tag*=(tr[tot].cs&1?-1ll:1ll),tr[tot<<1|1].tag*=(tr[tot].cs&1?-1ll:1ll);
        tr[tot].cs=0;
    }
    if(upd[tot]&&l<=nl&&nr<=r){
        tr[tot].cs+=1;
        tr[tot].v+=tr[tot].tag,tr[tot].tag*=-1ll;
        return ;
    }
    if(nl==nr){
        tr[tot].v+=mu[tr[tot].v];
        if(mu[tr[tot].v]==0){
            upd[tot]=1,tr[tot].tag=0;
            return;
        }
        ll nxt=tr[tot].v+mu[tr[tot].v],nnxt=nxt+mu[nxt];
        if(nnxt==tr[tot].v){
            upd[tot]=1;
            tr[tot].tag=mu[tr[tot].v];
        }
        return ;
    }
    if(mid>=l)update(nl,mid,tot<<1,l,r);
    if(mid<r)update(mid+1,nr,(tot<<1)|1,l,r);
    tr[tot].v=tr[tot<<1].v+tr[(tot<<1)|1].v;
    if(upd[tot<<1]&&upd[tot<<1|1]){
        upd[tot]=1;
        tr[tot].tag=tr[tot<<1].tag+tr[tot<<1|1].tag;
    }
}

ll Sum(int nl,int nr,int tot,int l,int r){
    ll mid=(nl+nr)>>1,res=0;
    if(tr[tot].cs&&nl!=nr){
        tr[tot<<1].v+=tr[tot<<1].tag*(tr[tot].cs&1?1ll:0ll),tr[tot<<1|1].v+=tr[tot<<1|1].tag*(tr[tot].cs&1?1ll:0ll);
        tr[tot<<1].cs+=tr[tot].cs,tr[(tot<<1)|1].cs+=tr[tot].cs;
        tr[tot<<1].tag*=(tr[tot].cs&1?-1ll:1ll),tr[tot<<1|1].tag*=(tr[tot].cs&1?-1ll:1ll);
        tr[tot].cs=0;
    }
    if(l<=nl&&nr<=r)return tr[tot].v;
    if(mid>=l)res+=Sum(nl,mid,tot<<1,l,r);
    if(mid<r)res+=Sum(mid+1,nr,(tot<<1)|1,l,r);
    return res;
}

void get_mu()
{
    
    mu[1]=1;
    vis[1]=true;
    for(int i=2;i<=5e6+10;i++)
    {
        if(!vis[i])
        {
            pr[++tot]=i;
            vis[i]=true;
            mu[i]=-1;
        }
        for(int j=1;j<=tot&&i*pr[j]<=5e6+10;j++)
        {
            vis[i*pr[j]]=true;
            if(i%pr[j]==0)
            {
                mu[i*pr[j]]=0;
                break;
            }
            else
            {
                mu[i*pr[j]]=-mu[i];
            }
        }
    }
    return ;
} 

vector<int> g[(int)1e5+9];

void dfs1(int u,int fa,int deep){
    dep[u]=deep,f[u]=fa,sz[u]=1;
    int ma=0;
    for(auto it:g[u]){
        if(it!=fa){
            dfs1(it,u,deep+1);
            sz[u]+=sz[it];
            if(ma<sz[it]){
                ma=sz[it],son[u]=it;
            }
        }
    }
}

void dfs2(int u,int fa){
    top[u]=fa,id[u]=++cnt,cov[id[u]]=u;
    if(!son[u])return ;
    dfs2(son[u],fa);
    for(auto it:g[u]){
        if(it!=son[u]&&it!=f[u]){
            dfs2(it,it);
        }
    }

}

void add(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        update(1,n,1,id[top[u]],id[u]);
        u=f[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    update(1,n,1,id[u],id[v]);
}

ll query(int u,int v){
    ll res=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        res+=Sum(1,n,1,id[top[u]],id[u]);
        u=f[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    res+=Sum(1,n,1,id[u],id[v]);
    return res;
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    get_mu();
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
	for(int i=2,x,y;i<=n;++i){
        cin>>x>>y;
        g[x].push_back(y),g[y].push_back(x);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,n,1);
    cin>>q;
    for(int i=1,x,y,z;i<=q;++i){
        cin>>x>>y>>z;
        if(x&1){
            add(y,z);
        }else cout<<query(y,z)<<"\n";
    }
    return 0;
}
0%