6360

waar

13934342708

solicitude羁绊
hhchaos1

vscode_growing

zst_2001
ljw-

zir
papapiu

1小时前

3天前

#include<bits/stdc++.h>

using namespace std;

#define eps 1e-5
#define x first
#define y second

const int N=1e5+10,M=2*N;

typedef long long ll;
typedef pair<ll,ll> pll;

int n,q;
int h[N];
struct node{
int op;
ll a;
int b;

}input[N];

struct node2{
ll cnt,sum;
}tr[M<<2];

vector<int> alls;

int find(int x){
return lower_bound(alls.begin(),alls.end(),x)-alls.begin();
}

void modify(int p, int l,int r,int i,int x,int y){
if(l==r){
tr[p].cnt+=x;
tr[p].sum+=y;
return;
}
int mid=(l+r)>>1;

if(i<=mid) modify(p*2,l,mid,i,x,y);
else modify(p*2+1,mid+1,r,i,x,y);
tr[p].cnt=tr[p*2].cnt+tr[p*2+1].cnt;
tr[p].sum=tr[p*2].sum+tr[p*2+1].sum;
}

pll ask(int p,int l,int r,int L,int R){
if(L<=l&&r<=R){
return {tr[p].cnt,tr[p].sum};
}
int mid=(l+r)>>1;
ll cnt=0,sum=0;
if(L<=mid) {
cnt+=t.x;
sum+=t.y;
}
if(R>=mid+1){
cnt+=t.x;
sum+=t.y;
}

return {cnt,sum};
}

bool check(double x,ll v){
int d=x>alls.back()?alls.back():x;
int i=find(d);
double v1=x*t.x-t.y;
if(v1>=v) return true;
return false;
}

int main(){
scanf("%d%d",&n,&q);

for(int i=1;i<=n;i++){
scanf("%d",&h[i]);
alls.push_back(h[i]);
}

for(int i=0;i<q;i++){
int op;
scanf("%d",&op);
if(op==1){
ll a;
int b;
scanf("%lld%d",&a,&b);
input[i]={op,a,b};
alls.push_back(b);
}
else{
ll a;
scanf("%lld",&a);
input[i]={op,a,0};
}
}

sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());

for(int i=1;i<=n;i++){
int j=find(h[i]);
modify(1,0,alls.size()-1,j,1,h[i]);
}

for(int i=0;i<q;i++){
auto u=input[i];
if(u.op==1){
int j=find(h[u.a]);
modify(1,0,alls.size()-1,j,-1,-h[u.a]);
h[u.a]=u.b;
j=find(u.b);
modify(1,0,alls.size()-1,j,1,u.b);
}
else{
double lb=0,ub=1e24+10;
while(ub-lb>=eps){
double mid=(lb+ub)/2;
check(mid,u.a)?ub=mid:lb=mid;
}
printf("%.5lf\n",ub);
}
}

return 0;
}



3天前
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
const int N=10005,M=4*N;

int n;
struct node{
int l,r;
}in[N];
vector<int > alls;
bool st[N];

int ans;

int lz[M<<2];

int find(int x){
return lower_bound(alls.begin(),alls.end(),x)-alls.begin();
}

void modify(int p,int l,int r,int L,int R,int id){
if(L<=l&&R>=r){
lz[p]=id;
return;
}

if(lz[p]!=-1){
lz[p<<1]=lz[p<<1|1]=lz[p];
lz[p]=-1;
}

int mid=(l+r)>>1;
if(L<=mid) modify(p<<1,l,mid,L,R,id);
if(R>mid) modify(p<<1|1,mid+1,r,L,R,id);
}

int dfs(int p,int l,int r){
if(lz[p]!=-1){
if(!st[lz[p]]){
st[lz[p]]=true;
return 1;
}
else return 0;
}
if(l==r) return 0;
int mid=(l+r)>>1;
return dfs(p<<1,l,mid) + dfs(p<<1|1,mid+1,r);
}

int main(){

int t;
scanf("%d",&t);

while(t--){
alls.clear();
ans=0;
memset(st,false,sizeof st);
scanf("%d",&n);
for(int i=0;i<n;i++){
int l,r;
scanf("%d%d",&l,&r);
in[i]={l,r};
alls.push_back(l);
alls.push_back(r);
alls.push_back(r+1);
}

sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());

memset(lz,-1,sizeof lz);

for(int i=0;i<n;i++){
int l=find(in[i].l), r=find(in[i].r);
modify(1,0,alls.size()-1,l,r,i);
}

printf("%d\n",dfs(1,0,alls.size()-1););
}

return 0;
}



3天前
#include<iostream>
#include<bitset>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=1e5+10,M=2*N,T=31;

int n,m,q;
bitset<T> ans[M<<2];
int lz[M<<2];

inline void make_tag(int p,int color){
lz[p]=color;
ans[p].reset();
ans[p].set(color-1,1);
}

void down(int p){
if(lz[p]){
make_tag(p<<1,lz[p]), make_tag(p<<1|1,lz[p]);
lz[p]=0;
}
}

void modify(int p,int l,int r,int L,int R,int color){
if(L<=l&&R>=r){
make_tag(p,color);
return;
}

down(p);

int mid=(l+r)>>1;
if(L<=mid) modify(p<<1,l,mid,L,R,color);
if(R>mid) modify(p<<1|1,mid+1,r,L,R,color);

ans[p]=ans[p<<1]|ans[p<<1|1];
}

bitset<T> ask(int p,int l,int r,int L,int R){
if(L<=l&&R>=r) return ans[p];

down(p);

bitset<T> res;
int mid=(l+r)>>1;

return res;
}

int main(){

scanf("%d%d%d",&n,&m,&q);
modify(1,1,n,1,n,1);

while(q--){
char s[2];
scanf("%s",s);
if(*s=='C'){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(b<a) swap(a,b);
scanf("%d%d%d",&a,&b,&c);
modify(1,1,n,a,b,c);
}
else{
int a,b;
scanf("%d%d",&a,&b);
if(b<a) swap(a,b);
}
}

return 0;
}


5天前
维护两个标记，
1.区间覆盖(置0，置1)，覆盖时，翻转标记清除
2.区间翻转，翻转时，如果有覆盖标记，直接翻转覆盖标记，否则，翻转标记取反

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10,M=N*3;

typedef long long ll;

int n;
struct node{
int op;
ll l,r;
}in[N];
vector<ll> alls;

struct node2{
int la,lb;
int cnt;
node2():la(-1),lb(0),cnt(0){}
}tr[M<<2];

int find(ll x){
return lower_bound(alls.begin(),alls.end(),x)-alls.begin();
}

void down(int p,int l,int r){
if(tr[p].la!=-1){
tr[p<<1].la=tr[p<<1|1].la=tr[p].la;
tr[p<<1].lb=tr[p<<1|1].lb=0;

int mid=(l+r)>>1;

if(tr[p].la==1){
tr[p<<1].cnt=mid-l+1;
tr[p<<1|1].cnt=r-mid;
}
else tr[p<<1].cnt=tr[p<<1|1].cnt=0;
tr[p].la=-1;
}

if(tr[p].lb){
int mid=(l+r)>>1;

if(tr[p<<1].la!=-1) tr[p<<1].la^=1;
else tr[p<<1].lb^=1;
tr[p<<1].cnt=mid-l+1-tr[p<<1].cnt;

if(tr[p<<1|1].la!=-1) tr[p<<1|1].la^=1;
else tr[p<<1|1].lb^=1;
tr[p<<1|1].cnt=r-mid-tr[p<<1|1].cnt;
tr[p].lb=0;
}

}

void modify(int p,int l,int r,int L,int R,int op){
if(L<=l&&r<=R){
if(op==1){
tr[p].lb=0;
tr[p].la=1;
tr[p].cnt=r-l+1;
}
else if(op==2){
tr[p].lb=0;
tr[p].la=0;
tr[p].cnt=0;
}
else{
if(tr[p].la!=-1) tr[p].la^=1;
else tr[p].lb^=1;
tr[p].cnt=r-l+1-tr[p].cnt;
}
return;
}

down(p,l,r);
int mid=(l+r)>>1;
if(L<=mid) modify(p<<1,l,mid,L,R,op);
if(R>=mid+1) modify(p<<1|1,mid+1,r,L,R,op);

tr[p].cnt=tr[p<<1].cnt+tr[p<<1|1].cnt;
}

if(l==r) {
return l;
}
down(p,l,r);
int mid=(l+r)>>1;
}

int ask2(int p,int l,int r,int x){
printf("%d %d %d\n",l,r,tr[p].cnt);
if(l==r) {
printf("%d, %d\n",alls[l],tr[p].cnt);
return l;
}
down(p,l,r);
int mid=(l+r)>>1;
}

int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
int op;
ll l,r;
scanf("%d%lld%lld",&op,&l,&r);
in[i]={op,l,r};
alls.push_back(l);
alls.push_back(r);
alls.push_back(r+1);
}
alls.push_back(1);

sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());

for(int i=0;i<n;i++){
auto &u=in[i];
int l=find(u.l), r=find(u.r);
modify(1,0,alls.size()-1,l,r,u.op);
printf("%lld\n",alls[p]);
}

return 0;
}


5天前

#include<bits/stdc++.h>

using namespace std;
const int N=5e3+10;

int n;
int a[N],cnt[N];
int ans[N];

int main(){

scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);

for(int i=1;i<=n;i++){
memset(cnt,0,sizeof cnt);
int id=i,mmax=-1;
for(int j=i;j<=n;j++){
int u=a[j];
cnt[u]++;
if(cnt[u]>mmax){
id=u;
mmax=cnt[u];
}
else if(cnt[u]==mmax&&u<id) id=u;
ans[id]++;
}
}

for(int i=1;i<=n;i++) printf("%d%c",ans[i],i==n?'\n':' ');

return 0;
}


7天前
#include<bits/stdc++.h>

using namespace std;

#define mod 11380
const int N=12,M=32;

int L1,L2,L3,D;
int f[N][N][N][M];

int main(){

scanf("%d%d%d%d",&L1,&L2,&L3,&D);

for(int i=0;i<=D;i++) f[0][0][0][i]=1;
for(int i=0;i<=L1;i++){
for(int j=0;j<=L2;j++){
for(int k=0;k<=L3;k++){
for(int d=1;d<=D;d++){

for(int c=0;c<=k-1;c++){
int t=f[0][0][c][d-1]*f[i][j][k-c-1][d]%mod;
f[i][j][k][d]=(f[i][j][k][d]+t)%mod;
}

for(int b=0;b<=j-1;b++){
for(int c=0;c<=k;c++){
int t=f[0][b][c][d-1]*f[i][j-b-1][k-c][d]%mod;
f[i][j][k][d]=(f[i][j][k][d]+t)%mod;
}
}

for(int a=0;a<=i-1;a++){
for(int b=0;b<=j;b++){
for(int c=0;c<=k;c++){
int t=f[a][b][c][d-1]*f[i-a-1][j-b][k-c][d]%mod;
f[i][j][k][d]=(f[i][j][k][d]+t)%mod;
}
}
}

}
}
}
}

printf("%d\n",D?(f[L1][L2][L3][D]+-f[L1][L2][L3][D-1]+mod)%mod:f[L1][L2][L3][D]);

return 0;
}


8天前
#include<bits/stdc++.h>

using namespace std;

const int N=6e4+10;

int v[100],cnt;
bool f[N];

int main(){

while(true){
int sum=0;
cnt=0;
for(int i=1;i<=6;i++){
int s;
scanf("%d",&s);
sum+=s*i;
int k=1;
while(k<=s){
v[++cnt]=k*i;
s-=k;
k*=2;
}
if(s>0) v[++cnt]=s*i;
}
if(!sum) return 0;

if(sum%2){
puts("Can't");
continue;
}
int m=sum/2;
memset(f,0,sizeof f);
f[0]=true;
for(int i=1;i<=cnt;i++){
for(int j=m;j>=v[i];j--){
f[j]=f[j]|f[j-v[i]];
}
}
if(f[m]) puts("Can");
else puts("Can't");
}

return 0;
}


9天前

1. AcWing 313. 花店橱窗
Time: 2023.05.23
描述：n类花按顺序排成一排放在m个花盆里，给出每类花在不同花盆的美观度，求美观度和的最大值。
f[i,j]：= 第i类花只考虑放在前j个花瓶时的美观度最大值;
状态计算: f[i,j] = max{v[i,k] + f[i-1}[k-1]},
要留出i-1个花瓶放前面的花，计算好k的范围，i<=k<=j;
2. AcWing 318. 划分大理石
Time: 2023.05.25
描述：6种大理石价值为1-6，给出每种大理石数量，问能否分成两堆使价值相等。
乍一看是多重背包的计数dp，用f[i][j]表示只考虑选前i类大理石作为其中一堆的所有方案中，
价值刚好为j的方案数。但是方案数过大，会爆答案，只要有一种就可以了,用bool来存储；
不过物品个数和价值都很大，TLE了。用二进制拆分来优化，变成01背包。
bool f[i][j] := 只考虑选前i类大理石作为其中一堆的所有方案中，是否存在价值刚好为j的方案；
状态计算：f[i][j] = f[i-1][j] | f[i-1][j-vi];
f[1-6][0] = true;
3. AcWing 317. 陨石的秘密
Time:2023.05.26
描述：给你i对{},j对[],k对(),深度d，构造一字符串，满足[]里不能有(),{}里不能有[]和()
求字符串深度为d的方案数。


    f[i][j][k][d] := 由i对{},j对[],k对()构成，深度<=d的字符串的方案数;
ans = f[i][j][k][d] - f[i][j][k][d-1];
以左边第一个括号的类型划分集合；S = (A)B, [A]B, {A}B，3种情况的方案数累加起来。
以[A]B为例，此时A没有{}，f[i][j][k][d] += ΣbΣc f[0][b][c][d-1]*f[i][j-b-1][k-c][d];


9天前
#include<bits/stdc++.h>

using namespace std;
const int N=1e2+10;

int n,m;
int f[N][N],pos[N][N],v[N][N];

void dfs(int i,int j){
int k=pos[i][j];
if(i-1>0) dfs(i-1,k-1);
if(i-1>0) putchar(' ');
printf("%d",k);
}

int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) scanf("%d",&v[i][j]);
}

for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=INT_MIN;
for(int k=i;k<=j;k++){
int t=v[i][k]+f[i-1][k-1];
if(t>f[i][j]){
f[i][j]=t;
pos[i][j]=k;
}
}
}
}

printf("%d\n",f[n][m]);
dfs(n,m);
for(int i=0;i<n;i++)

return 0;
}
`