如题,我莫名其妙全部TLE了,但是时间复杂度没有问题,校内oj通过,校内oj用的Linux系统,因此题为省选题,所以我认为测试数据相同,我用从校内oj上捞了几组数据,本地测试通过
#include<bits/stdc++.h>
#define ll long long
#define ls (u << 1)
#define rs ((u << 1) | 1)
using namespace std;
int read() {
int sign = 1, cnt = 0;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') {
sign = -1;
c = getchar();
}
}
while(isdigit(c)) {
cnt = cnt * 10 + (c ^ 48);
c = getchar();
}
return cnt * sign;
}
const int N = 1e5 + 10;
int a[N];
namespace tree{
struct node{
int l, r;
int maxn[2], lmaxn[2], rmaxn[2];
int sum, tag, rev;
}tr[N << 2];
void push_up(int u){
tr[u].sum = tr[ls].sum + tr[rs].sum;
tr[u].lmaxn[0] = tr[ls].lmaxn[0];
tr[u].lmaxn[1] = tr[ls].lmaxn[1];
if(tr[ls].lmaxn[0] == tr[ls].r - tr[ls].l + 1){
tr[u].lmaxn[0] += tr[rs].lmaxn[0];
}
if(tr[ls].lmaxn[1] == tr[ls].r - tr[ls].l + 1){
tr[u].lmaxn[1] += tr[rs].lmaxn[1];
}
tr[u].rmaxn[0] = tr[rs].rmaxn[0];
tr[u].rmaxn[1] = tr[rs].rmaxn[1];
if(tr[rs].rmaxn[0] == tr[rs].r - tr[rs].l + 1){
tr[u].rmaxn[0] += tr[ls].rmaxn[0];
}
if(tr[rs].rmaxn[1] == tr[rs].r - tr[rs].l + 1){
tr[u].rmaxn[1] += tr[ls].rmaxn[1];
}
tr[u].maxn[0] = max(max(tr[ls].maxn[0], tr[rs].maxn[0]), tr[ls].rmaxn[0] + tr[rs].lmaxn[0]);
tr[u].maxn[1] = max(max(tr[ls].maxn[1], tr[rs].maxn[1]), tr[ls].rmaxn[1] + tr[rs].lmaxn[1]);
}
void main_swap(int u){
swap(tr[u].maxn[1], tr[u].maxn[0]);
swap(tr[u].lmaxn[1], tr[u].lmaxn[0]);
swap(tr[u].rmaxn[1], tr[u].rmaxn[0]);
}
void addtag_turn(int u, int x){
tr[u].sum = (tr[u].r - tr[u].l + 1) * x;
tr[u].tag = x;
tr[u].rev = 0;
tr[u].maxn[x] = tr[u].lmaxn[x] = tr[u].rmaxn[x] = tr[u].r - tr[u].l + 1;
tr[u].maxn[!x] = tr[u].lmaxn[!x] = tr[u].rmaxn[!x] = 0;
}
void addtag_reverse(int u){
tr[u].sum = (tr[u].r - tr[u].l + 1) - tr[u].sum;
if(tr[u].tag != -1) tr[u].tag ^= 1;
else tr[u].rev ^= 1;
main_swap(u);
}
void push_down(int u){
if(tr[u].l == tr[u].r) return;
if(tr[u].tag != -1){
addtag_turn(ls, tr[u].tag);
addtag_turn(rs, tr[u].tag);
tr[u].tag = -1;
}
if(tr[u].rev){
addtag_reverse(ls);
addtag_reverse(rs);
tr[u].rev = 0;
}
}
void build(int u, int l, int r){
tr[u].l = l, tr[u].r = r;
tr[u].tag = -1;
tr[u].rev = 0;
if(l == r){
tr[u].sum = a[l];
tr[u].maxn[0] = tr[u].lmaxn[0] = tr[u].rmaxn[0] = (a[l] == 0) ? 1 : 0;
tr[u].maxn[1] = tr[u].lmaxn[1] = tr[u].rmaxn[1] = (a[l] == 1) ? 1 : 0;
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
push_up(u);
}
void update_turn(int u, int ql, int qr, int x){
if(tr[u].l >= ql && tr[u].r <= qr){
addtag_turn(u, x);
return;
}
push_down(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(mid >= ql) update_turn(ls, ql, qr, x);
if(mid < qr) update_turn(rs, ql, qr, x);
push_up(u);
}
void update_reverse(int u, int ql, int qr){
if(tr[u].l >= ql && tr[u].r <= qr){
addtag_reverse(u);
return;
}
push_down(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(mid >= ql) update_reverse(ls, ql, qr);
if(mid < qr) update_reverse(rs, ql, qr);
push_up(u);
}
int query_sum(int u, int ql, int qr){
if(tr[u].l >= ql && tr[u].r <= qr){
return tr[u].sum;
}
push_down(u);
int mid = (tr[u].l + tr[u].r) >> 1, ans = 0;
if(mid >= ql) ans += query_sum(ls, ql, qr);
if(mid < qr) ans += query_sum(rs, ql, qr);
return ans;
}
int query_maxn(int u, int ql, int qr){
if(tr[u].l >= ql && tr[u].r <= qr){
return tr[u].maxn[1];
}
push_down(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if(qr <= mid) return query_maxn(ls, ql, qr);
if(ql > mid) return query_maxn(rs, ql, qr);
int left = query_maxn(ls, ql, mid);
int right = query_maxn(rs, mid + 1, qr);
int cross = min(tr[ls].rmaxn[1], mid - ql + 1) + min(tr[rs].lmaxn[1], qr - mid);
return max({left, right, cross});
}
}
int main() {
// freopen("1858_7.in", "r", stdin);
// freopen("1.out", "w", stdout);
int n = read(), T = read();
for(int i = 1; i <= n; i++){
a[i] = read();
}
tree::build(1, 1, n);
while(T--){
int opt = read(), l = read(), r = read();
l++, r++;
switch(opt){
case 0: tree::update_turn(1, l, r, 0); break;
case 1: tree::update_turn(1, l, r, 1); break;
case 2: tree::update_reverse(1, l, r); break;
case 3: printf("%d\n", tree::query_sum(1, l, r)); break;
case 4: printf("%d\n", tree::query_maxn(1, l, r)); break;
}
}
return 0;
}
附上校内oj评测截图
蒟蒻已经快疯了。。。求调玄关。。。