本文共 2130 字，大约阅读时间需要 7 分钟。
每天增加m个灯泡，n个房间，能一次性换就换，模拟换灯泡过程。询问第几天的状态
离线做，按题意模拟。比赛时线段树写挫了。。导致不断超时，我太弱了。每次询问符合要求的最左边的点。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;typedef unsigned long long ull;#define ms(a, b) memset(a, b, sizeof(a))#define pb push_back#define mp make_pair#define pii pair //#define eps 0.0000000001#define IOS ios::sync_with_stdio(0);cin.tie(0);#define random(a, b) rand()*rand()%(b-a+1)+a#define pi acos(-1)//const ll INF = 0x3f3f3f3f3f3f3f3fll;const int inf = 0x3f3f3f3f;const int maxn = 1e5 + 10;const int maxm = 3000000 +10;const int mod = 998244353;struct ND{ int minn,l,r;}tree[maxn<<2];int n,m,k[maxn],d[maxn],q;void pushup(int rt){ tree[rt].minn=min(tree[rt<<1].minn,tree[rt<<1|1].minn);}void build(int rt,int l,int r){ tree[rt].l=l,tree[rt].r=r; if(l==r){ tree[rt].minn=k[l]; return; } int mid=(l+r)>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); pushup(rt);}void update(int rt,int pos,int val){ if(tree[rt].l==tree[rt].r){ tree[rt].minn=val; return; } int mid=(tree[rt].l+tree[rt].r)>>1; if(pos<=mid) update(rt<<1,pos,val); else update(rt<<1|1,pos,val); pushup(rt);}int query(int rt,int L,int R,ll val){ if(tree[rt].minn>val) return inf; if(tree[rt].l==tree[rt].r){ return tree[rt].l; } int mid=(tree[rt].l+tree[rt].r)>>1; if(tree[rt<<1].minn<=val&&L<=mid) return query(rt<<1,L,R,val); if(tree[rt<<1|1].minn<=val&&R>mid) return query(rt<<1|1,L,R,val);}pair ans[maxn];bool vis[maxn];int main() {#ifdef LOCAL freopen("input.txt", "r", stdin);// freopen("input.txt", "w", stdout);#endif scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&k[i]); scanf("%d",&q); for(int i=1;i<=q;i++) scanf("%d",&d[i]); build(1,1,n); memset(vis,false,sizeof(vis));// cout< =n) break; } for(int j=1;j<=q;j++){ if(d[j]>=i){ printf("%d %lld\n",ans[i].first,ans[i].second); }else{ printf("%d %lld\n",ans[d[j]].first,ans[d[j]].second); } } return 0;}
转载于:https://www.cnblogs.com/fht-litost/p/9585003.html