奥兹古德,最后大魔王,正二十面体展开图
time limit: 6000/3000 ms (java/others) memory limit: 502768/502768 k (java/others)
total submission(s): 3636 accepted submission(s): 1612
我要评论 1 #include <iostream>
2 #include <stdio.h>
3 #include <math.h>
4 #include <string.h>
5 #include <stdlib.h>
6 #include <string>
7 #include <vector>
8 #include <set>
9 #include <map>
10 #include <queue>
11 #include <algorithm>
12 #include <sstream>
13 #include <stack>
14 using namespace std;
15 #define rep(i,a,n) for (int i=a;i<n;i++)
16 #define per(i,a,n) for (int i=n-1;i>=a;i--)
17 #define pb push_back
18 #define mp make_pair
19 #define all(x) (x).begin(),(x).end()
20 #define fi first
21 #define se second
22 #define sz(x) ((int)(x).size())
23 #define fo freopen("in.txt", "r", stdin);
24 #define debug(x) cout << "&&" << x << "&&" << endl;
25 #define lowbit(x) (x&-x)
26 #define mem(a,b) memset(a, b, sizeof(a));
27 typedef vector<int> vi;
28 typedef long long ll;
29 typedef pair<int,int> pii;
30 const ll mod=1000000007;
31 const int inf = 0x3f3f3f3f;
32 ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
33 ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
34 //head
35
36 const int n=100010;
37 int b[n];
38 int sum[n<<2],sub[n<<2],lazy[n<<2];//区间和 区间最小值 lazy标记
39
40 void pushup(int rt) {//上传
41 sum[rt]=sum[rt<<1]+sum[rt<<1|1];//左右孩子之和
42 sub[rt]=min(sub[rt<<1],sub[rt<<1|1]);//左右孩子的最小值
43 }
44
45 void pushdown(int rt) {//下压
46 lazy[rt<<1]+=lazy[rt];//传标记
47 lazy[rt<<1|1]+=lazy[rt];
48 sub[rt<<1]-=lazy[rt];//更新 因为是每次减一 所以就直接减lazy
49 sub[rt<<1|1]-=lazy[rt];
50 lazy[rt]=0;//清除父节点标记
51 }
52
53 void build(int rt,int l,int r) {
54 sum[rt]=0;//rt的初始状态
55 lazy[rt]=0;
56 if(l==r) {
57 scanf("%d",&b[l]);//建树的一种方式
58 sub[rt]=b[l];
59 return;
60 }
61 int mid=(l+r)>>1;//递归建树
62 build(rt<<1,l,mid);
63 build(rt<<1|1,mid+1,r);
64 pushup(rt);//因为不涉及修改，不需要下压，只需上传
65 }
66
67 void dfs(int rt,int l,int r) {
68 if(l==r) {
69 sum[rt]++;
70 sub[rt]=b[l];
71 return;
72 }
73 int mid=(l+r)>>1;
74 pushdown(rt);
75 if(!sub[rt<<1]) dfs(rt<<1,l,mid);
76 if(!sub[rt<<1|1]) dfs(rt<<1|1,mid+1,r);
77 pushup(rt);
78 }
79
80 void updata(int rt,int l,int r,int l,int r) {//l，r为时时变动的区间
81 if(l>=l&&r<=r) {//如果当前节点在待查询节点内
82 lazy[rt]++;
83 sub[rt]--;
84 if(!sub[rt]) dfs(rt,l,r);//如果区间最小值为0，递归搜索位置
85 return;
86 }
87 int mid=(l+r)>>1;//递归找l,r的涉及区间
88 pushdown(rt);//需要走左右孩子，先下压
89 if(l<=mid) updata(rt<<1,l,mid,l,r);
90 if(r>mid) updata(rt<<1|1,mid+1,r,l,r);
91 pushup(rt);//走完之后，状态上传给父亲节点
92 }
93
94 int query(int rt,int l,int r,int l,int r) {
95 if(l>=l&&r<=r) //待查询区间内
96 return sum[rt];
97 int mid=(l+r)>>1;
98 pushdown(rt);//走左右孩子
99 int ans=0;
100 if(l<=mid) ans+=query(rt<<1,l,mid,l,r);
101 if(r>mid) ans+=query(rt<<1|1,mid+1,r,l,r);
102 pushup(rt);//走完，状态上传给父亲节点
103 return ans;
104 }
105
106
107 int main() {
108 int n,q;
109 while(~scanf("%d%d",&n,&q)) {
110 build(1,1,n);
111 char s[10];
112 int a,b;
113 while(q--) {
114 scanf("%s%d%d",s,&a,&b);
115 if(s[0]=='a') updata(1,1,n,a,b);
116 else printf("%d\n",query(1,1,n,a,b));
117 }
118 }
119 }
上面用了dfs搜索最小值为0的位置，也可以一直去找。
1 void update(int l,int r,int l,int r,int rt)
2 {
3 if(a[rt]>1&&l<=l&&r<=r)
4 {
5 lazy[rt]++;
6 a[rt]--;
7 return;
8 }
9 if(a[rt]==1&&l==r)
10 {
11 sum[rt]++;
12 lazy[rt]=0;
13 a[rt]=b[l];
14 return;
15 }
16 int mid=(l+r)>>1;
17 pushdown(rt);
18 if(l<=mid)update(l,r,l,mid,rt<<1);
19 if(r>mid)update(l,r,mid+1,r,rt<<1|1);
20 pushup(rt);
21 }
！！！！这里的变量含义和第一个代码不一样。自行理解。
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论