Starry

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

dsu on tree

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
#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,c[(int)1e5+9],sz[(int)1e5+9],son[(int)1e5+9],cnt[(int)1e5+9],mx,res,ans[(int)1e5+9];
vector<int> g[(int)1e5+9];

void dfs(int u,int fa){
    for(auto it:g[u])if(it!=fa)dfs(it,u),sz[u]+=sz[it],son[u]=sz[son[u]]<sz[it]?it:son[u];
    sz[u]+=1;
}

void cal(int u,int fa,int val,int bson){
    cnt[c[u]]+=val;
    if(cnt[c[u]]>mx)res=c[u],mx=cnt[c[u]];
    else if(cnt[c[u]]==mx)res+=c[u];
    for(auto it:g[u]){
        if(it!=fa&&it!=bson)cal(it,u,val,bson);
    }
}

void dfs2(int u,int fa,int opt){
    for(auto it:g[u])if(it!=fa&&it!=son[u])dfs2(it,u,1);
    if(son[u])dfs2(son[u],u,0);
    cal(u,fa,1,son[u]);
    ans[u]=res;
    if(opt)cal(u,fa,-1,0),res=0,mx=0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>c[i];
    for(int i=1,x,y;i<n;++i){
        cin>>x>>y;
        g[x].push_back(y),g[y].push_back(x);
    }
    dfs(1,0);
    dfs2(1,0,0);
    for(int i=1;i<=n;++i)cout<<ans[i]<<" \n"[i==n];
    return 0;
}

发表于 更新于 分类于 本文字数： 423 阅读时长 ≈ 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
91
92
93
94
95
96
97
98
99
100
101
102
103
//1787 D. Game on Axis
#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 tt,n,a[(int)2e5+9],son[(int)2e5+9];
bitset<(int)2e5+9> vis;

struct dsu{
	vi fa,sz;
	dsu(int n){
		fa.resize(n+1),sz.resize(n+1);
		for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1;
	}
	int fnd(int x){
		return fa[x]==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;
	}
};

vi g[(int)2e5+9];

ll dfs(ll u,ll &ans){
	ll res=0;
	for(auto it:g[u]){
		res+=dfs(it,ans);
		if(!vis[it])son[u]+=son[it];
	}
	ans+=res*son[u];
	son[u]+=!vis[u];
	return res+(vis[u]);
}

void solve(){
	cin>>n;
	dsu d(n);
	vector<int> cycle;
	f(i,1,n)cin>>a[i];
	f(i,1,n)a[i]+=i;
	f(i,1,n)if(1<=a[i]&&a[i]<=n){g[a[i]].push_back(i);}
	f(i,1,n)son[i]=0ll;
	bool ok=true;
	vis.reset();
	ll ans=0,cnt=0,sz=0,p=1,lst=1;
	for(;1<=p&&p<=n;vis[p]=1,lst=p,p=a[p],sz+=1)if(vis[p]){ok=false;break;}

	if(ok)dfs(lst,ans);
	vis.reset();
	for(int i=1;i<=n;++i){
		if(1<=a[i]&&a[i]<=n)if(!d.merge(i,a[i]))cycle.push_back(d.fnd(i));
	}
	for(auto it:cycle)vis[d.fnd(it)]=1;
	for(int i=1,x;i<=n;++i)x=d.fnd(i),cnt+=(x!=d.fnd(1)&&!vis[x]);
	if(!ok)ans+=(cnt+1ll+n)*sz;
	else {
		ans+=(cnt+1ll+n)*sz+(n-sz)*(2ll*n+1ll)+(sz)*(sz-1ll)/2;

	}
	cout<<ans<<"\n";
	f(i,1,n)g[i].clear();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(sb,1,tt)solve();
    return 0;
}

发表于 更新于 分类于 本文字数： 510 阅读时长 ≈ 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
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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const ll inf = 1e18;

template < typename T, auto op, auto e, typename F, auto mapping, auto composition,
           auto e1 >
class segtree
{
    int n;
    vector< T > v;
    vector< F > lazy;
    void build(int now, int l, int r, T a[])
    {
        if(l == r)
        {
            v[now] = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(now * 2, l, mid, a);
        build(now * 2 + 1, mid + 1, r, a);
        v[now] = op(v[now * 2], v[now * 2 + 1]);
    }
    void pushup(int k) { v[k] = op(v[k * 2], v[k * 2 + 1]); }
    void pushdown(int k, int l, int r)
    {
        v[k] = mapping(v[k], lazy[k], l, r);
        if (l != r) {
            lazy[k * 2] = composition(lazy[k * 2], lazy[k]);
            lazy[k * 2 + 1] = composition(lazy[k * 2 + 1], lazy[k]);
        }
        lazy[k] = e1();
    }

    void modify(int now, int ql, int qr, int l, int r, F x)
    {
        pushdown(now, l, r);
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            lazy[now] = x;
            pushdown(now, l, r);
            return;
        }
        modify(now * 2, ql, qr, l, (l + r) / 2, x);
        modify(now * 2 + 1, ql, qr, (l + r) / 2 + 1, r, x);
        pushup(now);
    }
    T query(int now, int ql, int qr, int l, int r)
    {
        pushdown(now, l, r);
        if (l > qr || r < ql) return e();
        if (l >= ql && r <= qr) return v[now];
        return op(query(now * 2, ql, qr, l, (l + r) / 2),
                  query(now * 2 + 1, ql, qr, (l + r) / 2 + 1, r));
    }

public:
    segtree(T a[], int n) : segtree(n)
    {
        build(1, 1, n, a);
    }
    segtree(int n)
    {
        this->n = n;
        v = vector< T >(n << 2, e());
        lazy = vector< F >(n << 2, e1());
    }

    void modify(int l, int r, F x) { modify(1, l, r, 1, n, x); }
    T query(int l, int r) { return query(1, l, r, 1, n); }
};

template<typename T>
T MAX(T x, T y) {if(x > y) return x; else return y;}
template<typename T>
T MIN(T x, T y) {if(x < y) return x; else return y;}
template<typename T>
T PLUS(T x, T y) {return x + y;}

/*  Note:
    typename T, auto op, T e, 
    typename F, auto mapping, auto composition,
    F e1
*/
struct F {ll add, cover;};
using segtree_max_edit=segtree< ll, [](ll x, ll y) { return max(x, y); }, [](){return -inf;}, F,
         [](ll x, F t, int l, int r) {
             if (t.cover != inf)
                 return t.cover;
             else
                 return x + t.add;
         },
         [](F t1, F t2) -> F {
             if (t2.cover != inf) return{ 0, t2.cover };
             else 
             {
                 if (t1.cover != inf) return { 0, t1.cover + t2.add };
                 else return { t1.add + t2.add, inf };
             }
         }, 
         []()->F {return { 0, inf };} >;

ll n,q,a[(int)1e6+9];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;++i)cin>>a[i];
    segtree_max_edit seg(a,n);
    for(int i=1,op,l,r,x;i<=q;++i){
        cin>>op>>l>>r;
        if(op==1){
            cin>>x;
            seg.modify(l,r,F{0,x});
        }else if(op==2){
            cin>>x;
            seg.modify(l,r,F{x,inf});
        }else cout<<seg.query(l,r)<<"\n";
    }
}

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

需要O2优化

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
vector<double> st[(int)1e3+9];

ll n,m,id[(int)1e5+9],fk,l[(int)1e5+9],r[(int)1e5+9];
double a[(int)1e5+9];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	fk=sqrt(n*log(n)/2);
	for(int i=1;i<=n;++i){
		id[i]=(i-1)/fk+1;
		if(!l[id[i]])l[id[i]]=i;
		r[id[i]]=i;
	}
	for(int i=1,x,y;i<=m;++i){
		cin>>x>>y;
		auto &it=st[id[x]];
		a[x]=1.0*y/(x*1.0);
		it.clear();
		for(int j=l[id[x]];j<=r[id[x]];++j){
			if(a[j]==0.0)continue;
			if(it.empty()||it.back()<a[j])it.push_back(a[j]);
		}
		ll ans=0;
		double mx=0.0;
		for(int j=1;j<=id[n];++j){
			auto &aa=st[j];
			if(!aa.empty()){
				ans+=aa.end()-upper_bound(aa.begin(),aa.end(),mx);
				mx=max(mx,aa.back());
			}
		}
		cout<<ans<<"\n";
	}
}

发表于 更新于 分类于 本文字数： 189 阅读时长 ≈ 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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const int maxn=1e5+9;

double mx[maxn<<2];
ll ans[maxn<<2],n,m;

ll query(int l,int r,int k,double ma){
	if(mx[k]<=ma)return 0;
	if(l==r)return 1;
	else if(mx[k<<1]<=ma)return query(((l+r)>>1)+1,r,k<<1|1,ma);
	return query(l,(l+r)>>1,k<<1,ma)+ans[k]-ans[k<<1];
}

void change(int l,int r,int k,int x,double val){
	if(l==x&&r==x)return ((void)(ans[k]=1,mx[k]=val));
	int mid=(l+r)>>1;
	if(x<=mid)change(l,mid,k<<1,x,val);
	else change(mid+1,r,k<<1|1,x,val);
	mx[k]=max(mx[k<<1],mx[k<<1|1]);
	ans[k]=ans[k<<1]+query(mid+1,r,k<<1|1,mx[k<<1]);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1,x,y;i<=m;++i){
		cin>>x>>y;
		change(1,n,1,x,(y*1.0)/(x*1.0));
		cout<<ans[1]<<"\n";
	}
}
0%