xj集合

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long int ll;
 4 const ll inf=1E18;
 5 int n,m,totC;
 6 ll f[2005*50],g[2005*50];
 7 struct pt
 8 {
 9     int type,c;
10     ll w,v;
11     bool operator<(const pt&A)const
12     {
13         return w==A.w?type<A.type:w<A.w;
14     }
15 }a[4005];
16 inline void solve()
17 {
18     sort(a+1,a+n+m+1);
19     for(int i=0;i<=totC;++i)
20         f[i]=-inf;
21     f[0]=0;
22     int tot=0;
23     for(int i=n+m;i>=1;--i)
24         if(a[i].type==0)
25         {
26             int c=a[i].c,v=a[i].v;
27             for(int j=0;j<=tot-c;++j)
28                 f[j]=max(f[j],f[j+c]+v);
29         }
30         else
31         {
32             int c=a[i].c,v=a[i].v;
33             tot+=c;
34             for(int j=tot;j>=c;--j)
35                 f[j]=max(f[j],f[j-c]-v);
36         }
37     ll ans=-inf;
38     for(int i=0;i<=totC;++i)
39         ans=max(ans,f[i]);
40     cout<<ans<<endl;
41 }
42 int main()
43 {
44 //    freopen("a.in","r",stdin);
45 //    ios::sync_with_stdio(false);
46     cin>>n>>m;
47     for(int i=1;i<=n;++i)
48     {
49         cin>>a[i].c>>a[i].w>>a[i].v;
50         totC+=a[i].c;
51         a[i].type=1;
52     }
53     for(int i=n+1;i<=n+m;++i)
54     {
55         cin>>a[i].c>>a[i].w>>a[i].v;
56         a[i].type=0;
57     }
58     solve();
59     return 0;
60 }

  1 #include<bits/stdc++.h>
  2 #define mod 998244353
  3 using namespace std;
  4 typedef long long int ll;
  5 const int maxn=2E5+5;
  6 int n,m,tag[maxn*4];
  7 ll a[maxn];
  8 int loop[maxn*4][24],rem[maxn*4],hh[maxn];
  9 bool ok[maxn*4];
 10 inline int read()
 11 {
 12     char ch=getchar();
 13     while(!isdigit(ch))ch=getchar();
 14     int s=ch-‘0‘;ch=getchar();
 15     while(isdigit(ch)){s=s*10+ch-‘0‘;ch=getchar();}
 16     return s;
 17 }
 18 int G[55];
 19 inline void write(int x)
 20 {
 21     int g=0;
 22     do{G[++g]=x%10;x/=10;}while(x);
 23     for(int i=g;i>=1;--i)putchar(‘0‘+G[i]);putchar(‘\n‘);
 24 }
 25 ll tmp[24];
 26 inline void put(int num,int x)
 27 {
 28     tag[num]+=x;
 29     for(int i=0;i<24;++i)
 30         tmp[i]=loop[num][(i+x)%24];
 31     for(int i=0;i<24;++i)
 32         loop[num][i]=tmp[i];
 33     rem[num]=loop[num][0];
 34 }
 35 inline void pushup(int num)
 36 {
 37     ok[num]=ok[num<<1]&ok[num<<1|1];
 38     rem[num]=rem[num<<1]+rem[num<<1|1];
 39     rem[num]-=rem[num]>=mod?mod:0;
 40     if(ok[num])
 41     {
 42         for(int i=0;i<24;++i)
 43             loop[num][i]=loop[num<<1][i]+loop[num<<1|1][i];
 44         for(int i=0;i<24;++i)
 45             loop[num][i]-=loop[num][i]>=mod?mod:0;
 46     }
 47 }
 48 inline void pushdown(int num)
 49 {
 50     int x=tag[num];
 51     if(x==0)
 52         return;
 53     tag[num]=0;
 54     put(num<<1,x),put(num<<1|1,x);
 55 }
 56 void build(int l,int r,int num)
 57 {
 58     if(l==r)
 59     {
 60         hh[l]=24;
 61         rem[num]=a[l];
 62         return;
 63     }
 64     int mid=(l+r)>>1;
 65     build(l,mid,num<<1),build(mid+1,r,num<<1|1);
 66     pushup(num);
 67 }
 68 void change(int L,int R,int l,int r,int num)
 69 {
 70     if(L<=l&&r<=R&&ok[num])
 71     {
 72         put(num,1);
 73         return;
 74     }
 75     if(l==r)
 76     {
 77         a[l]=a[l]*a[l]%mod;
 78         --hh[l];
 79         if(hh[l]==0)
 80         {
 81             ok[num]=1;
 82             ll x=a[l];
 83             for(int i=0;i<24;++i,x=x*x%mod)
 84                 loop[num][i]=x;
 85         }
 86         rem[num]=a[l];
 87         return;
 88     }
 89     pushdown(num);
 90     int mid=(l+r)>>1;
 91     if(R<=mid)
 92         change(L,R,l,mid,num<<1);
 93     else if(mid<L)
 94         change(L,R,mid+1,r,num<<1|1);
 95     else
 96         change(L,R,l,mid,num<<1),change(L,R,mid+1,r,num<<1|1);
 97     pushup(num);
 98 }
 99 ll ask(int L,int R,int l,int r,int num)
100 {
101     if(L<=l&&r<=R)
102         return rem[num];
103     pushdown(num);
104     int mid=(l+r)>>1;
105     if(R<=mid)
106         return ask(L,R,l,mid,num<<1);
107     else if(mid<L)
108         return ask(L,R,mid+1,r,num<<1|1);
109     return ask(L,R,l,mid,num<<1)+ask(L,R,mid+1,r,num<<1|1);
110 }
111 int main()
112 {
113 //    freopen("nagato2.in","r",stdin);
114 //    freopen("a.out","w",stdout);
115     ios::sync_with_stdio(false);
116     n=read(),m=read();
117     for(int i=1;i<=n;++i)
118         a[i]=read();
119     build(1,n,1);
120     while(m--)
121     {
122         int opt=read(),l=read(),r=read();
123         if(opt==1)
124             change(l,r,1,n,1);
125         else
126             write(ask(l,r,1,n,1)%mod);
127     }
128     return 0;
129 }