【HDOJ】3275 Light

时间:2024-11-13 18:33:56

这就是个简单线段树+延迟标记。因为对bool使用了~而不是!,wa了一下午找不到原因。

 /* 3275 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 typedef struct {
bool f;
int ln, tot;
} node_t; const int maxn = 1e5+;
char s[maxn];
node_t nd[maxn<<];
int L, R; inline void PushUp(int rt) {
nd[rt].ln = nd[rt<<].ln + nd[rt<<|].ln;
} inline void PushDown(int rt) {
if (nd[rt].f) {
int lb = rt<<;
int rb = lb|;
nd[lb].f = !nd[lb].f;
nd[lb].ln = nd[lb].tot - nd[lb].ln;
nd[rb].f = !nd[rb].f;
nd[rb].ln = nd[rb].tot - nd[rb].ln;
nd[rt].f = false;
}
} void Build(int l, int r, int rt) {
nd[rt].f = false;
nd[rt].tot = r - l + ;
if (l == r) {
nd[rt].ln = (s[l] == '');
return ;
} int mid = (l + r) >> ;
Build(lson);
Build(rson); PushUp(rt);
} int Query(int l, int r, int rt) {
if (l == r)
return l; PushDown(rt);
int mid = (l + r) >> ;
int ret; if (nd[rt<<].ln == nd[rt<<].tot)
ret = Query(rson);
else
ret = Query(lson);
PushUp(rt); return ret;
} void Update(int l, int r, int rt) {
if (L<=l && R>=r) {
nd[rt].f = !nd[rt].f;
nd[rt].ln = nd[rt].tot - nd[rt].ln;
return ;
} PushDown(rt);
int mid = (l + r) >> ; if (R <= mid) {
Update(lson);
} else if (L > mid) {
Update(rson);
} else {
Update(lson);
Update(rson);
} PushUp(rt);
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int n, l;
int ans, k; while (scanf("%d %d",&n,&l)!=EOF && (n||l)) {
scanf("%s", s+);
Build(, n, );
if (nd[].tot == nd[].ln) {
puts("");
continue;
}
if (l == ) {
puts("-1");
continue;
} ans = ;
while () {
++ans;
k = Query(, n, );
L = k;
R = L + l - ;
#ifndef ONLINE_JUDGE
// printf("k = %d\n", k);
#endif
if (R > n) {
ans = -;
break;
}
Update(, n, );
if (nd[].tot == nd[].ln)
break;
}
printf("%d\n", ans);
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}