比较好的一道贪心题.
有 3 种操作：
1. 对一个位置赋值.
2. 对一个位置进行加法.
3. 对一个位置进行乘法.
显然，如果想让结果最大，顺序一定是 1,2,3 即先赋值再加最后乘.
3 种情况同时存在不好比较，那么考虑将所有操作都转换成乘法.
假设一个操作加了 $x$，另一个操作乘了 $y$，则操作后分别为：
$tot+frac{tot}{a_{i}} imes x$ 与 $tot imes y$.
除掉 $tot$ 后，为:$frac{a_{i}+x}{a_{i}}$ 与 $y$，所以加法操作可以转换为：$frac{a_{i}+x}{a_{i}}$.
但是这个 $a_{i}$ 是不固定的，那么考虑对位置 $i$ 进行的所有加法及赋值操作：
1. 一定是先赋值，再加（如果有赋值的话）
2. 第一次赋值（也只会赋值一次）可以看作是一次加法，然后先加大的，后加小的.
可以把赋值当作一次加法和其他加法一起排序（如果赋值在后面且选了赋值可以看作是先赋了这个值，后进行的前面的加法）.
处理好每一个位置的加法/赋值操作后和所有乘法扔到数组里排序，取前 m 个即可.
注意输出的时候要先输出加法及赋值，后输出乘法来保证最优性.
code:
#include <set>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100009
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
struct data {
int opt,x,y;
}a[N];
struct node {
double x;
int id;
node(double x=0,int id=0):x(x),id(id){}
bool operator<(const node b) const {
return x==b.x?id<b.id:x>b.x;
}
};
int arr[N],ma[N];
bool cm(int i,int j) {
return a[i].opt<a[j].opt;
}
vector<int>add[N];
vector<int>ans;
set<node>se;
set<node>::iterator it;
bool cmp(int i,int j) {
return a[i].y>a[j].y;
}
int main() {
// setIO("input");
int k,n,m;
scanf("%d%d%d",&k,&n,&m);
for(int i=1;i<=k;++i) scanf("%d",&arr[i]);
for(int i=1;i<=n;++i) {
scanf("%d%d%d",&a[i].opt,&a[i].x,&a[i].y);
if(a[i].opt==1&&a[ma[a[i].x]].y<a[i].y) {
ma[a[i].x]=i;
}
}
for(int i=1;i<=n;++i) {
if(a[i].opt==1) {
if(i==ma[a[i].x]&&a[i].y>arr[a[i].x]) {
a[i].y-=arr[a[i].x];
add[a[i].x].push_back(i);
}
}
if(a[i].opt==2) {
add[a[i].x].push_back(i);
}
if(a[i].opt==3) {
se.insert(node(1.00*a[i].y,i));
}
}
for(int i=1;i<=k;++i) {
sort(add[i].begin(),add[i].end(),cmp);
ll p=arr[i];
for(int j=0;j<add[i].size();++j) {
se.insert(node((double)(p+a[add[i][j]].y)/p,add[i][j]));
p+=a[add[i][j]].y;
}
}
printf("%d
",min((int)se.size(),m));
int cnt=1;
for(it=se.begin();it!=se.end()&&cnt<=m;it++) {
ans.push_back((*it).id);
++cnt;
}
sort(ans.begin(),ans.end(),cm);
for(int i=0;i<ans.size();++i) printf("%d ",ans[i]);
return 0;
}