Starry

发表于 更新于 分类于 本文字数： 210 阅读时长 ≈ 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
#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,x,y,z,k,s; 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(S,1,tt){
    	cin>>x>>y>>z>>k>>s;
    	if(x+y*s<k){
    		cout<<x+y*s<<"\n";
    	}else if(x-z*s>=k){
    		cout<<x-z*s<<"\n";
    	}
    	else {
    		ll mi=k-z,ma=k-1+y,l=0,r=s;
    		while(l<r){
    			ll mid=(l+r)>>1,tmp=x+mid*y-(s-mid)*z;
    			if(tmp>ma){
    				r=mid;
    			}else if(tmp<mi){
    				l=mid;
    			}else break;
    		}
    		ll mid=(l+r)>>1,tmp=x+mid*y-(s-mid)*z;
    		cout<<tmp<<"\n";
    	}
    }
    return 0;
}

发表于 更新于 分类于 本文字数： 375 阅读时长 ≈ 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
#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;

const int maxn=2e5+9;
int n,m,rt[maxn],cnt,b[maxn],a[maxn],tot;
struct Node{
	int l,r,val;
}tr[maxn*20];

inline void build(int &k,int l,int r){
	k=++cnt;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(tr[k].l,l,mid),build(tr[k].r,mid+1,r);
}


inline void change(int &k,int kk,int l,int r,int val){
	k=++cnt,tr[k]=tr[kk],tr[k].val+=1;
	if(l==r)return ;
	int mid=(l+r)>>1;
	if(val<=mid)change(tr[k].l,tr[kk].l,l,mid,val);
	else change(tr[k].r,tr[kk].r,mid+1,r,val);
}

inline int query(int nl,int nr,int l,int r,int k){
	int x=tr[tr[nr].l].val-tr[tr[nl].l].val;
	if(l==r)return b[l];
	int mid=(l+r)>>1;
	if(x>=k)return query(tr[nl].l,tr[nr].l,l,mid,k);
	return query(tr[nl].r,tr[nr].r,mid+1,r,k-x);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    f(i,1,n)cin>>a[i],b[i]=a[i];
    sort(b+1,b+1+n);
    tot=unique(b+1,b+n+1)-(b+1);
    build(rt[0],1,tot);
    f(i,1,n){
    	int now=lower_bound(b+1,b+1+tot,a[i])-b;
    	change(rt[i],rt[i-1],1,tot,now);
    }
    for(int i=1,l,r,k;i<=m;++i){
    	cin>>l>>r>>k;
    	cout<<query(rt[l-1],rt[r],1,tot,k)<<"\n";
    }
    return 0;
}

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

离线操作dfs

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
#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)1e6+9],m,ans[(int)1e6+9];
std::vector<int> g[(int)1e6+9];
struct opt
{
	int opt,wz,val;
}e[(int)1e6+9];

void dfs(int x){
	auto [aa,bb,cc]=e[x];
	if(aa==2)ans[x]=a[bb];
	else ans[x]=-1;
	if(aa==1){
		ll tmp=a[bb];
		a[bb]=cc;
		for(auto it :g[x])dfs(it);
		a[bb]=tmp;
	}else{
		for(auto it :g[x])dfs(it);
	}
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    f(i,1,n)cin>>a[i];
    for(int i=1,x,y,z,w;i<=m;++i){
    	cin>>x>>y>>z;
    	if(y==1){
    		cin>>w;
    	}
    	g[x].push_back(i);
    	e[i]={y,z,w};
    }
    dfs(0);
    f(i,1,m)if(~ans[i])cout<<ans[i]<<"\n";
    return 0;
}

发表于 更新于 分类于 本文字数： 232 阅读时长 ≈ 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
#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,a[(int)1e5+9];

struct BIT
{
    ll  h[(int)1e5 + 9];
    void update(int x,int k)
    {
        while(x<=n){
            h[x]=k;
            int low=lowbit(x);
            for(int i=1;i<low;i<<=1)h[x]=max(h[x],h[x-i]);
            x+=lowbit(x);
        }  
    }
    ll gmin(int l, int r)
    {
        ll ans = 0;
        while (r >= l)
        {
            ans = max(ans, a[r]);
            r--;
            while (r - lowbit(r) >= l)
            {
                ans = max(h[r], ans);
                r -= lowbit(r);
            }
        }
        return ans;
    }
}b;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    f(i,1,n){
        cin>>a[i];
    }
    f(i,1,n)b.update(i,a[i]);
    for(int i=1,x,y;i<=m;++i){
        cin>>x>>y;
        cout<<b.gmin(x,y)<<"\n";
    }
    return 0;
}

发表于 更新于 分类于 本文字数： 242 阅读时长 ≈ 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
#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,a[(int)1e5+9],f[(int)1e5+9][21],lo[(int)1e5+9];

inline ll rmq(int l,int r){
	int k=lo[r-l+1];
	return max(f[l][k],f[r-(1ll<<k)+1][k]);
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
	for(int i=1;i<=n;++i)f[i][0]=a[i];
    for(int i=2;i<=n;++i)lo[i]=lo[i>>1]+1;
    for(int j=1;j<=20;++j){
    	for(int i=1;i+(1ll<<j)-1<=n;++i){
    		f[i][j]=max(f[i][j-1],f[i+(1ll<<(j-1))][j-1]);
    	}
    }
    for(int i=1,x,y;i<=m;++i){
    	scanf("%d%d",&x,&y);
    	printf("%lld\n",rmq(x,y));
    }
    return 0;
}
0%